HDU ACM 2121 Ice_cream’s world II （无根最小树形图）

【解题思路】这题先看了NotOnlySuccess的解题思路，即设置虚根再处理的做法；弄了一个上午，再次有种赶脚的感觉~~如果需要找出为什么需要去比所有权值之和更大的数为新增的虚边的话，一开始我理解仅是找比最大边权值要大的数就够了，因为这样就已经满足了不会提前找到虚边的情况，但如果是这样的话那就很难判断这样一种情况：生成的最小树形图（含虚根）有两条边是从虚根出来的。

  1 #include<cstdio>
  2 #include<cstring>
  3 #define SIZE 1002
  4 #define MAXN 20004
  5 
  6 using namespace std;
  7 
  8 const int INF = 1<<30;
  9 int nv, ne, aimroot;
 10 int vis[SIZE], pre[SIZE], num[SIZE];
 11 int inLength[SIZE];
 12 
 13 struct Edge{
 14     int u, v, w;
 15 }edge[MAXN];
 16 
 17 
 18 void addedge(int u, int v, int w)
 19 {//添加虚根与原图中其他点相连的边 
 20     edge[ne].u = u;
 21     edge[ne].v = v;
 22     edge[ne].w = w;
 23     return;
 24 }
 25 
 26 bool Traverse(int& res, int root)
 27 {
 28     nv++;
 29     while(true)
 30     {
 31         for(int i=0; i<nv; ++i) inLength[i] = INF;
 32         for(int i=0; i<ne; ++i)
 33         {
 34             int& u = edge[i].u;
 35             int& v = edge[i].v; 
 36             if(edge[i].w < inLength[v] && u != v)
 37             {
 38                 //不管结点的Id号怎样变化，固定的边所在的位置是不会变的，根据边在edge数组中存储的位置与起初边的Id号的对应关系
 39                 //就能理解下面为什么要这样输出 
 40                 if(u == root) aimroot = i;
 41                 inLength[v] = edge[i].w;
 42                 pre[v] = u;
 43             }
 44         }
 45         for(int i=0; i<nv; ++i)
 46         if(i != root && inLength[i] == INF) return false;
 47         int newnum = 0;
 48         inLength[root] = 0;
 49         memset(vis, -1, sizeof(vis));
 50         memset(num, -1, sizeof(num));
 51         for(int i=0; i<nv; ++i)
 52         {
 53             res += inLength[i];
 54             int v = i;
 55             while(vis[v] != i && num[v] == -1 && v != root)
 56             {
 57                 vis[v] = i;
 58                 v = pre[v];
 59             }
 60             if(vis[v] == i)
 61             {
 62                 for(int u=pre[v]; u != v; u = pre[u])
 63                     num[u] = newnum;
 64                 num[v] = newnum++;
 65             }
 66         }    
 67         if(newnum == 0) return true;
 68         for(int i=0; i<nv; ++i)
 69         if(num[i] == -1) num[i] = newnum++;
 70         for(int i=0; i<ne; ++i)
 71         {
 72             int u = edge[i].u;
 73             int v = edge[i].v;
 74             edge[i].u = num[u];
 75             edge[i].v = num[v];
 76             if(edge[i].u != edge[i].v)
 77                 edge[i].w -= inLength[v];
 78         }
 79         nv = newnum;
 80         root = num[root];
 81     }
 82 
 83 }
 84 
 85 int main()
 86 {
 87     #ifndef ONLINE_JUDGE
 88     freopen("input.txt", "r", stdin);
 89     #endif
 90     while(scanf("%d%d", &nv, &ne) != EOF)
 91     {
 92         int u, v, w, sum = 0;
 93         for(int i=0; i<ne; ++i)
 94         {
 95             scanf("%d%d%d", &u, &v, &w);
 96             edge[i].u = u;
 97             edge[i].v = v;
 98             edge[i].w = u == v ? INF+1 : w;
 99             sum += w;
100         }
101         sum++;
102         int temp = ne;
103         for(int i=0; i<nv; ++i, ++ne)
104             addedge(nv, i, sum);
105         int res = 0;
106         //res < 2*sum 设立这个条件是因为考虑到这种情况，虚根引出两条出边，这是不允许的，必须承认这是虚根，你得在原图中找到一个根
107         //这个条件成立了，说明有两条以上的虚边引出 
108         if(Traverse(res, nv) && res < 2*sum) 
109         //结合上面addedge函数中的说明，得到的aimroot存储的是你初始新存储虚边是在edge的下标，此下标大于或等于原图边的数目（边是从
110         //从零下标开始存储 
111             printf("%d %d

", res-sum, aimroot-temp);
112         else 
113             printf("impossible

");
114     }
115     return 0;
116 }