卡了我好几天的最小树形图........
这题是要找出最小树形图，而且如果有多种情况，输出根编号最小的一棵。这是当时个人赛的题目，赛后才知道这是最小树形图，还知道这种图的算法是中国人研发的，叫做朱刘算法。算法很容易理解，不过我一直都没尝试做几个题目。前几天，回想起个人赛有一道最小树形图的题目，于是便打算拿这题来试刀。
朱刘算法是O(VE)的一个算法，最糟糕的时候要计算V*E次，最理想的状态就是直接E次的边查找，恰好构造出无环的最小树形图。
刚开始打的代码是研究一本模板后，根据思想和变量的设定来尝试打出来。第一次，是直接抄模板，试试看模板能不能用。对这道题，我刚开始是用暴力朱刘算法的方法，也就是更换V次根来找最小树形图。当然，O(V^2E)的复杂度是必然过不了的。那时想不到这题（不定根的最小树形图）可以有一个十分巧妙的方法来解决，就是添加一个虚拟根，然后把虚拟根指向到每一个顶点处。不过这样还没完，添加的每条边都要赋予相同的权值，表明每个顶点都有机会充当根。这时还要考虑的一个问题就是，边权到底要多少呢？答案是明显的，是越大越好，同时要保证计算不会溢出，那就可以了。于是，我们可以设置一个比所有真实的边权的和要大一点的值。
我的代码是参考这个博客写出来的：http://www.cnblogs.com/wuyiqi/archive/2011/09/07/2169708.html
我打这题一共重打了4次，前几次都是参照刚开始学的模板的储存方式来打的。不过，TLE了好多次，修改了也好多次，发现还是过不了，于是我就模仿上面的链接里的代码来写。两种思想是一样的，不过，博客的是储存边，直接用边处理的，而模板的是储存点和点的关系的。我看了一下，发现直接储存边好像更加优越。
于是，今天下午我去机房的时候顺便尝试储存边的方法切了这题。第一次写，环的处理方法跟博客的处理方法不一样，又TLE，十分郁闷！当时猜想，应该是某些数据使得程序死循环了吧。因为我之前写的几次都是有漏洞的，而且我很容易就构造出死循环的数据。我不想再纠结这个问题太久了，所以我再看多一遍博客的方法，确定能够记住了后，自己就像默写一样，几乎一样的将代码打了一遍。不过，这次还是没有很好的记住，需要我debug。debug着，太累了，然后睡了两个小时..... - - 起来后，我再添加一点debug的信息，终于被我发现问题。改过来以后，测试了几组数据，过了，交上去，也过了！
终于，今天我解决了这个卡了好几天的问题。这不是难，应该是我对算法理解不够透彻，所以一直不能debug出问题。
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <iostream> 6 7 typedef __int64 ll; 8 const int maxv = 1100; 9 const int maxe = 12000; 10 const ll inf = 0x7f7f7f7f; 11 12 int in[maxv], vis[maxv], pre[maxv], fold[maxv], pos; 13 // in-arc's cost pre-vex new vex-num 14 ll min_cost; 15 struct edge{ 16 int b, e; 17 ll c; 18 }E[maxe]; 19 // save arcs 20 21 bool make_tree(int root, int v, int e){ 22 int cnt; 23 24 min_cost = 0; 25 while (true){ 26 for (int i = 0; i < v; i++){ 27 in[i] = inf; 28 pre[i] = -1; 29 } // suppose every vex does not have pre-vex 30 for (int i = 0; i < e; i++){ 31 int s = E[i].b; 32 int t = E[i].e; 33 34 if (in[t] > E[i].c && s != t){ 35 in[t] = E[i].c; 36 pre[t] = s; 37 if (s == root){ 38 pos = i; 39 } // record the vex whose pre-vex is the vertual root by using the edge's number 40 } 41 } // find the min-in-arc of every vex 42 #ifndef ONLINE_JUDGE 43 for (int i = 0; i < v; i++){ 44 printf("pre %d : %d\n", i, pre[i]); 45 } 46 printf("root %d\n", root); 47 #endif 48 for (int i = 0; i < v; i++){ 49 vis[i] = -1, fold[i] = -1; 50 if (in[i] == inf && i != root) return false; 51 } // ensure whether the tree can be build, of course, it is no use in this problem 52 53 cnt = 0; 54 in[root] = 0; 55 for (int i = 0, j, k; i < v; i++){ 56 if (i == root) continue; 57 min_cost += in[i]; 58 vis[i] = i; 59 for (j = pre[i]; vis[j] != i && fold[j] == -1 && j != root; j = pre[j]){ 60 vis[j] = i; 61 } 62 if (j == root || fold[j] != -1) continue; 63 64 k = j; 65 for (fold[k] = cnt, k = pre[k]; k != j; k = pre[k]) fold[k] = cnt; 66 cnt++; 67 } // find circle and re-number every vex 68 #ifndef ONLINE_JUDGE 69 printf("cnt %d\n", cnt); 70 #endif 71 if (!cnt) return true; 72 for (int i = 0; i < v; i++){ 73 if (fold[i] == -1) fold[i] = cnt++; 74 } // re-number the rest single vex 75 for (int i = 0; i < e; i++){ 76 int s = E[i].b; 77 int t = E[i].e; 78 79 E[i].b = fold[s]; 80 E[i].e = fold[t]; 81 if (E[i].b != E[i].e) 82 E[i].c -= in[t]; 83 } // refresh every arcs 84 root = fold[root]; 85 v = cnt; 86 } 87 } 88 89 90 bool deal(){ 91 int n, m; 92 ll e_sum = 0; 93 94 if (scanf("%d%d", &n, &m) == EOF) return false; 95 for (int i = 0; i < m; i++){ 96 scanf("%d%d%I64d", &E[i].b, &E[i].e, &E[i].c); 97 E[i].b++; E[i].e++; 98 e_sum += E[i].c; 99 } 100 e_sum++; 101 for (int i = 0; i < n; i++){ 102 E[m + i].b = 0; 103 E[m + i].e = i + 1; 104 E[m + i].c = e_sum; 105 } // build virtual root 106 make_tree(0, n + 1, m + n); 107 if (min_cost < (e_sum << 1)){ 108 printf("%I64d %d\n", min_cost - e_sum, pos - m); 109 } 110 else puts("impossible"); 111 puts(""); 112 113 return true; 114 } 115 116 int main(){ 117 #ifndef ONLINE_JUDGE 118 freopen("in","r",stdin); 119 #endif 120 while (deal()); 121 122 return 0; 123 }
这是模板的方法，本地的一些比较刁难的数据都能通过，不过就是不知道怎样超时！留着，以后慢慢研究！
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 7 #define debug 0 8 9 typedef __int64 ll; 10 ll max2(ll a, ll b) {return a > b ? a : b; } 11 ll min2(ll a, ll b) {return a < b ? a : b; } 12 13 const int maxn = 1001; 14 const ll inf = 0x7f7f7f7f; 15 16 int in[maxn][maxn], out[maxn][maxn]; 17 // in-arc out-arc 18 ll cost[maxn][maxn], min_cost; 19 ll mf_arc[maxn]; 20 // min-fold-arc 21 int pre[maxn], fold[maxn]; 22 bool del[maxn], vis[maxn], mk[maxn]; 23 24 void init(int vn){ // initialize the variable 25 for (int i = 0; i <= vn; i++){ 26 in[i][0] = out[i][0] = 0; 27 del[i] = false; 28 pre[i] = fold[i] = i; 29 mf_arc[i] = inf; 30 for (int j = 0; j <= vn; j++){ 31 cost[i][j] = inf; 32 } 33 } 34 } 35 36 void min_tree(int vn, int &rt, int root){ 37 int i, j, k, cb, t, tmp; 38 bool cycle; 39 40 #if debug 41 for (i = 0; i <= vn; i++){ 42 for (j = 0; j <= vn; j++){ 43 if (cost[i][j] == inf) printf("inf "); 44 else printf("%3I64d ", cost[i][j]); 45 } 46 puts(""); 47 } 48 puts(""); 49 #endif 50 min_cost = 0; 51 while (true){ // run until no cycles 52 cycle = false; 53 for (i = 0; i <= vn; i++){ 54 if (del[i] || i == root) continue; 55 cost[i][i] = inf; 56 pre[i] = i; 57 for (j = 1; j <= in[i][0]; j++){ 58 if (del[in[i][j]]) continue; 59 if (cost[pre[i]][i] > cost[in[i][j]][i]){ 60 pre[i] = in[i][j]; 61 } 62 } 63 } // find the min-in-arc 64 #if debug 65 for (i = 1; i <= vn; i++){ 66 printf("%d : pre %d fold %d\n", i, pre[i], fold[i]); 67 } 68 puts(""); 69 #endif 70 for (i = 0; i <= vn; i++) vis[i] = false, mk[i] = false; 71 for (i = 0; i <= vn; i++){ 72 if (vis[i] || del[i] || i == root) continue; 73 for (j = pre[i]; !vis[j]; vis[j] = true, j = pre[j]); 74 cb = j;// suppose cb is cycle-begin 75 if (j == root || mk[j]) { 76 mk[i] = true; 77 continue; // if can reach the root, not cycle 78 } 79 cycle = true; 80 #if debug 81 printf("when i %d cycle begin at %d\n", i, cb); 82 printf("sub-vexs: "); 83 for (j = pre[cb]; j != cb; j = pre[j]) printf("%d ", j); 84 puts(""); 85 #endif 86 min_cost += cost[pre[cb]][cb]; 87 for (j = pre[cb]; j != cb; j = pre[j]){ 88 del[j] = true; 89 min_cost += cost[pre[j]][j]; 90 } 91 for (j = 1; j <= in[cb][0]; j++){ 92 if (del[in[cb][j]]) continue; 93 cost[in[cb][j]][cb] -= cost[pre[cb]][cb]; 94 if (!in[cb][j]){ 95 if (mf_arc[cb] > cost[in[cb][j]][cb]) 96 fold[cb] = fold[cb], mf_arc[cb] = cost[in[cb][j]][cb]; 97 else if (mf_arc[cb] == cost[in[cb][j]][cb]) 98 fold[cb] = min2(fold[cb], cb); 99 #if debug 100 printf("mf_arc %d : %I64d fold %d\n", cb, mf_arc[cb], fold[cb]); 101 #endif 102 } 103 } 104 cost[pre[cb]][cb] = 0; 105 for (j = pre[cb]; j != cb; j = pre[j]){ 106 for (k = 1; k <= out[j][0]; k++){ 107 t = out[j][k]; 108 if (del[t] || t == cb || t == root) continue; 109 if (cost[cb][t] == inf){ 110 out[cb][++out[cb][0]] = t; 111 in[t][++in[t][0]] = cb; 112 } 113 cost[cb][t] = min2(cost[cb][t], cost[j][t]); 114 } 115 for (k = 1; k <= in[j][0]; k++){ 116 t = in[j][k]; 117 if (del[t] || t == cb) continue; 118 if (cost[t][cb] == inf){ 119 in[cb][++in[cb][0]] = t; 120 out[t][++out[t][0]] = cb; 121 } 122 tmp = cost[t][j] - cost[pre[j]][j]; 123 cost[t][cb] = min2(cost[t][cb], tmp); 124 if (t == root){ 125 if (mf_arc[cb] > tmp) 126 fold[cb] = fold[j], mf_arc[cb] = tmp; 127 else if (mf_arc[cb] == tmp) 128 fold[cb] = min2(fold[j], fold[cb]); 129 #if debug 130 printf("sub_mf_arc %d : %I64d fold %d\n", cb, mf_arc[cb], fold[cb]); 131 #endif 132 } 133 } 134 cost[pre[j]][j] = 0; 135 } 136 #if debug 137 printf("fold %d out %d\n", cb, fold[cb]); 138 #endif 139 break; 140 } 141 if (!cycle){ 142 for (i = 0; i <= vn; i++){ 143 if (i == root || del[i]) continue; 144 min_cost += cost[pre[i]][i]; 145 if (pre[i] == root) rt = fold[i]; 146 } 147 break; 148 } 149 #if debug 150 printf("vex deleted: "); 151 for (i = 0; i <= vn; i++){ 152 if (del[i]) printf("%d ", i); 153 } 154 puts("\n"); 155 printf("min_cost %I64d\n", min_cost); 156 for (i = 0; i <= vn; i++){ 157 for (j = 0; j <= vn; j++){ 158 if (cost[i][j] == inf) printf("inf "); 159 else printf("%3I64d ", cost[i][j]); 160 } 161 puts(""); 162 } 163 puts(""); 164 #endif 165 } 166 #if debug 167 printf("min_cost %I64d\n", min_cost); 168 for (i = 0; i <= vn; i++){ 169 printf("%d : pre %2d fold %2d\n", i, pre[i], fold[i]); 170 } 171 puts(""); 172 #endif 173 } 174 175 176 int main(){ 177 int n, m; 178 int a, b, rt = 0; 179 ll c, sum; 180 181 while (~scanf("%d%d", &n, &m)){ 182 init(n); 183 sum = 0; 184 for (int i = 0; i < m; i++){ 185 scanf("%d%d%I64d", &a, &b, &c); 186 a++; b++; 187 sum += c; 188 cost[a][b] = min2(cost[a][b], c); 189 in[b][++in[b][0]] = a; 190 out[a][++out[a][0]] = b; 191 } 192 sum++; 193 #if debug 194 printf("sum %I64d\n", sum); 195 #endif 196 for (int i = 1; i <= n; i++){ 197 in[i][++in[i][0]] = 0; 198 out[0][++out[0][0]] = i; 199 cost[0][i] = sum; 200 } 201 #if debug 202 puts("in-arcs:"); 203 for (int i = 0; i <= n; i++){ 204 printf("%d : ", i); 205 for (int j = 1; j <= in[i][0]; j++){ 206 printf("%d ", in[i][j]); 207 } 208 puts(""); 209 } 210 puts(""); 211 #endif 212 min_tree(n, rt, 0); 213 if (min_cost < (sum << 1)){ 214 printf("%I64d %d\n", min_cost - sum, rt - 1); 215 } 216 else{ 217 puts("impossible"); 218 } 219 puts(""); 220 } 221 222 return 0; 223 }