POJ 3164 Command Network （最小树形图）

【解题思路】百度百科：最小树形图】里面有详细的解释，而Notonlysucess有精简的模板，下文有对其模板的一点解释，前提是对朱刘算法有所了解

【PS】这题没必要写题解，学了朱刘算法并不是表示你就锻炼到了思维了，在看最小树形图的形成时，对缩点那部分内容的算法和思路感叹不已，我想这就是算法的魅力！！

要理解的话，最好结合那张转载得很疯狂的图，但单看不行，自己将每个过程手动笔画一下更容易理解，开始搜题解的时候几乎都是用了模板，本来也想理解之后靠模板过了就算了以后如果遇到了这类题，二话不说直接上模板，后来自己还是手动的敲了一下，在OJ上提交了不差20次吧~~

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #define SIZE 102
  6 #define MAXN 1 << 14
  7 
  8 using namespace std;
  9 
 10 const double inf = 1 << 30;
 11 const double eps = 1e-8;
 12 int nv, m, ne, root, cnt;
 13 
 14 struct Edge{
 15     int u, v;
 16     double cost;
 17 };
 18 struct Edge edge[MAXN];
 19 double x[SIZE], y[SIZE];
 20 int vis[SIZE];
 21 int circle_id[SIZE];
 22 double node[SIZE][SIZE];
 23 double in[SIZE];
 24 int pre[SIZE];
 25 
 26 double dis(int a, int b)
 27 {
 28     return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
 29 }
 30 
 31 void dfs(int cur)
 32 {
 33     vis[cur] = 1;
 34     for(int i=1; i<=nv; ++i)
 35     if(!vis[i] && node[cur][i] > inf)
 36      dfs(i);
 37 }
 38 
 39 bool exit_circle(double& res)
 40 {
 41     int update_id = 1;
 42     memset(vis, -1, sizeof(vis));
 43     memset(circle_id, -1, sizeof(circle_id));
 44     in[root] = 0;
 45     for(int i=1; i<=nv; ++i)
 46     {
 47         res += in[i];
 48         int v = i;
 49         while(vis[v] != i && circle_id[v] == -1 && v != root)
 50         {
 51             vis[v] = i;
 52             v = pre[v];
 53         }
 54         if(vis[v] == i)
 55         {
 56             for(int u = pre[v]; u != v; u = pre[u])
 57                 circle_id[u] = update_id;
 58             circle_id[v] = update_id++;
 59         }
 60     }
 61     if(update_id == 1) return true;
 62     for(int i=1; i <= nv; ++i)
 63     if(circle_id[i] == -1)
 64     circle_id[i] = update_id++;
 65     
 66     for(int i=0; i < ne; ++i)
 67     {
 68         int u = edge[i].u;
 69         int v = edge[i].v;
 70         edge[i].u = circle_id[u];
 71         edge[i].v = circle_id[v];
 72         if(edge[i].u != edge[i].v) edge[i].cost -= in[v]; 
 73     }
 74     nv = update_id - 1;
 75     root = circle_id[root];
 76     return false; 
 77 }
 78 
 79 bool insert()
 80 {
 81     for(int i=1; i<=nv; ++i) in[i] = inf;
 82     for(int i=0; i<ne; ++i)
 83     {
 84         int& e = edge[i].v;
 85         if(e == root) continue;
 86         if(e != edge[i].u && in[e] > edge[i].cost)
 87         {
 88             in[e] = edge[i].cost;
 89             pre[e] = edge[i].u;
 90         }
 91     }
 92     for(int i=1; i <= nv; ++i)
 93         if(i != root && inf - in[i] < eps) return false;    
 94     return true;
 95 }
 96 
 97 int main()
 98 {
 99     while(scanf("%d%d", &nv, &ne) != EOF)
100     {
101         for(int i=1; i<=nv; ++i)
102             scanf("%lf%lf", &x[i], &y[i]);
103         cnt = 0;
104         memset(node, 0, sizeof(node));
105         for(int i=0; i<ne; ++i)
106         {
107             int u, v;
108             scanf("%d%d", &u, &v);
109             if(u != v)
110                 edge[i].cost = dis(u, v);
111             else 
112                 edge[i].cost = inf;
113             edge[i].u = u;
114             edge[i].v = v;
115         }
116         root = 1;
117         bool flag = false;
118         double ans = 0;
119         do
120         {
121             if(!insert())
122             {
123                 flag = true;
124                 break;
125             }
126         }while(!exit_circle(ans));
127         if(flag) printf("poor snoopy
");
128         else printf("%.2f
", ans);
129     }
130     return 0;    
131 }

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath> 
  4 #define SIZE 104
  5 #define MAXN 10002
  6 
  7 using namespace std;
  8 
  9 const double esp = 1e-10;
 10 const double inf = 1<<30;
 11 
 12 int nv, ne;
 13 
 14 struct Edge{
 15     int v, u;
 16     double cost;
 17 }edge[MAXN];
 18 
 19 int vis[SIZE], circle_id[SIZE];
 20 int pre[SIZE];
 21 double in[SIZE];
 22 double x[SIZE], y[SIZE];
 23 
 24 double dis(int v, int u)
 25 {
 26     return sqrt((x[v]-x[u])*(x[v]-x[u]) + (y[v]-y[u])*(y[v]-y[u]));
 27 }
 28 
 29 bool Traverse(double& res)
 30 {//基本来自于模板 
 31     int root = 1;
 32     while(true)
 33     {
 34         for(int i = 1; i <= nv; ++i) in[i] = inf+SIZE;
 35         for(int i = 0; i < ne; ++i)
 36         {//集当前结点的各自最小的入边 
 37             int& u = edge[i].u;
 38             if(in[u] > edge[i].cost && u != edge[i].v)
 39             {
 40                 in[u] = edge[i].cost;
 41                 pre[u] = edge[i].v;
 42             }
 43         }
 44         //在当前情况下如果有任何一个点没有最小边，说明不能形成最小树形图 
 45         //但这里没必要每次都判断，只在第一次进行判断即可 
 46         for(int i = 1; i <= nv; ++i)
 47         if(i != root && in[i] > inf) return false;
 48         
 49         int credit = 1;
 50         in[root] = 0;
 51         memset(vis, -1, sizeof(vis));
 52         memset(circle_id, -1, sizeof(vis));
 53         for(int i = 1; i <= nv; ++i)
 54         {//res为什么可以一直在加，首先第一次其就将有环没环的【结点最小边】的权值都加了，但就像缩点的理由所说的一样
 55          //环中没必要加的一条边再后来的减掉了，看下面的 ‘##’处 
 56             res += in[i];
 57             int v = i;
 58             while(vis[v] != i && circle_id[v] == -1 && v != root)
 59             {//这里并不能将 circle_id[v] == -1 这个条件提取出来提前判断
 60              //一个结点假设其不在环内，那么其结果是退后到根点或者退后到一个结点是环内点（已判断其为环内的点） 
 61                 vis[v] = i;
 62                 v = pre[v];
 63             }
 64             if(vis[v] == i)
 65             {//其实这里已经在缩点，将环内的点写入一个统一的结点编号 
 66                 for(int u = pre[v]; u != v; u = pre[u])
 67                     circle_id[u] = credit;
 68                 circle_id[v] = credit++;
 69             }
 70         }
 71         if(credit == 1) return true;
 72         for(int i = 1; i <= nv; ++i)
 73         if(circle_id[i] == -1) circle_id[i] = credit++;
 74         for(int i = 0; i < ne; ++i)
 75         {//如果更新后两个结点有相同的编号，其作用体现在上面求最小边中 ：u != edge[i].v的判断 
 76             int u = edge[i].u;
 77             int v = edge[i].v;
 78             edge[i].u = circle_id[u];
 79             edge[i].v = circle_id[v];
 80             // ## 如果这条最小边不在环内（即这里判断的意义），因为之前加了最小边的值，那就得减去其值。
 81             //那么减掉之后就可能变成了零或比之前短 ；其实这里不用判断条件的 如果是在环内
 82             //其因为两端的结点相同对后来没有了影响，这是剩下最后一种情况了，就是一结点在环内（能缩点的条件） 
 83             if(edge[i].v != edge[i].u)
 84                 edge[i].cost -= in[u];
 85         }
 86         nv = credit - 1;
 87         root = circle_id[root];
 88     }
 89     return true;
 90 }
 91 
 92 
 93 int main()
 94 {
 95     while(scanf("%d%d", &nv, &ne) != EOF)
 96     {
 97         for(int i = 1; i <= nv; ++i)
 98             scanf("%lf%lf", &x[i], &y[i]);
 99         for(int i = 0; i < ne; ++i)
100         {//这里就开始处理掉自环的情况，把自环的距离设置得比预定的最大值还大 
101             scanf("%d%d", &edge[i].v, &edge[i].u);
102             edge[i].cost = edge[i].v == edge[i].u ? inf+MAXN : dis(edge[i].v, edge[i].u);
103         }
104         double res = 0;
105         if(Traverse(res)) printf("%.2f
", res); //这里用f好像跟提交的方式有关，FAQ里有解释 
106         else printf("poor snoopy
");
107     }
108     return 0;    
109 }