处理这样一类问题：

给一个有向图，定义树形图：一个有向图以x为根的树形图，是一个n-1条边的集合，使得x能到达其他每一个点

树形图的权值定义为边的和

朱刘算法就是求最小树形图

 

方法：

1.给每个点p找一个边权最小的连向它的边，边权为val，前驱设为pre。找到了一个边集E0

ans记录总权值

2.检查，如果有一个孤立点（除了rt），那么无解，退出

如果没有有向环，那么完毕。当前的ans就是答案。退出

3.对于每一个有向环，缩点

4.更新新图的权值：枚举所有的边，如果x，y缩点之后不是一个点，那么e[i].v-=val[y]，象征，如果再选择这个点，那么就把环上的这个边删掉。

重复以上过程，直到退出

（5.如果要输出方案，那么在没有有向环之后，要把缩的点再展开大概用边来记录替换的信息，递归处理就可以吧，，，）

 

复杂度：O(nm)可能远远不到这个上界

正确性：由于有反悔操作，所以直接贪心就正确了。

代码：

poj3164 Command Network

不能用快读，否则会TLE。。。辣鸡poj

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=105;const int M=1e5+5;const int inf=2000000000;struct node{    int x,y;    double v;}e[M];int id[N],vis[N],pre[N];double val[N];double px[N],py[N];int n,m;double ans;int cnt;double dist(int a,int b){    return sqrt((double)(px[a]-px[b])*(px[a]-px[b])+(double)(py[a]-py[b])*(py[a]-py[b]));}double wrk(int rt,int n){    double ret=0;//    printf("%.10lf",val[0]);    int turn=0;    while(1){        ++turn;    //    cout<<" turn "<
           
            <<" "<
            
             <<" rt "<<
             
              e[i].v){ val[e[i].y]=e[i].v; pre[e[i].y]=e[i].x; } } } for(reg i=0;i
             
            
           
          
         
        
       
      

或者可以用dfs判环，类似tarjan

复杂度一定有保证：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=105;const int M=1e4+5;struct node{    int x,y;    double v;}e[M];int id[N],vis[N],pre[N];bool in[N];double val[N];double px[N],py[N];int n,m;double ans;int sta[N],top;int cnt;double dist(int a,int b){    return sqrt((double)(px[a]-px[b])*(px[a]-px[b])+(double)(py[a]-py[b])*(py[a]-py[b]));}void dfs(int x){//    cout<<" x "<
           
            <
            
             e[i].v){ val[e[i].y]=e[i].v; pre[e[i].y]=e[i].x; } } }// for(reg i=1;i<=n;++i){// cout<
             <<" : "<
              
               <<" : "<
               
                <
               
              
            
           
          
         
        
       
      

 

正常一点的模板：

luoguP4716 【模板】最小树形图

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=105;const int M=1e4+5;struct node{    int x,y;    int v;}e[M];int id[N],vis[N],pre[N];bool in[N];int val[N];int n,m;int rt;int sta[N],top;int cnt;void dfs(int x){//    cout<<" x "<
           
            <
            
             e[i].v){ val[e[i].y]=e[i].v; pre[e[i].y]=e[i].x; } } }// for(reg i=1;i<=n;++i){// cout<
             <<" : "<
              
               <<" : "<
               
                <
               
              
            
           
          
         
        
       
      

 

（一个看似弱智的问题：为什么prim不能用？因为无向图可以用的原因是，两边都可以走。有向图会堵住一边。使得第一次出队不一定最优

尝试这个图：

 

）

 

扩展：如果根不定呢？

超级源点，向每个点连接sum(w)+1的边

由于很大，所以最多连一条这样的边

如果最后权值>=sum(w)+sum(w)+1，那么实际上是无解的。

---

upda：2019.5.6

最小树形图：O(n+mlogn)算法

入边整体-Wmin

从0边不断往上reduce

到根？直接缩链为点

有环？ρ形，边权都是0

先都要上

缩环

所有入边可并堆合并起来，再整体减去Wmin（整体标记）

所有出边用并查集，需要的时候直接定位到这个缩完的点上

每次-Wmin，就是减去入边的最小权值，因为必然会选择恰好一次

最后所有减过的Wmin之和就是ans（因为实际上连接的都是0权边，没有额外贡献）