首页 > ACM题库 > HDU-杭电 > hdu 2121 Ice_cream’s world II-最小树形图[解题报告]C++
2013
12-29

hdu 2121 Ice_cream’s world II-最小树形图[解题报告]C++

Ice_cream’s world II

问题描述 :

After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.

输入:

Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.

输出:

Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.

样例输入:

3 1
0 1 1

4 4
0 1 10
0 2 10
1 3 20
2 3 30

样例输出:

impossible

40 0

  卡了我好几天的最小树形图……..

  这题是要找出最小树形图,而且如果有多种情况,输出根编号最小的一棵。这是当时个人赛的题目,赛后才知道这是最小树形图,还知道这种图的算法是中国人研发的,叫做朱刘算法。算法很容易理解,不过我一直都没尝试做几个题目。前几天,回想起个人赛有一道最小树形图的题目,于是便打算拿这题来试刀。

  朱刘算法是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出问题。

#include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <cstdlib>
 #include <iostream>
 
 typedef __int64  ll;
 const int maxv = 1100;
 const int maxe = 12000;
 const ll inf = 0x7f7f7f7f;
 
 int in[maxv], vis[maxv], pre[maxv], fold[maxv], pos;
 //   in-arc's cost              pre-vex      new vex-num
 ll min_cost;
 struct edge{
     int b, e;
     ll c;
 }E[maxe];
 // save arcs
 
 bool make_tree(int root, int v, int e){
     int cnt;
 
     min_cost = 0;
     while (true){
         for (int i = 0; i < v; i++){
             in[i] = inf;
             pre[i] = -1;
         } // suppose every vex does not have pre-vex
         for (int i = 0; i < e; i++){
             int s = E[i].b;
             int t = E[i].e;
 
             if (in[t] > E[i].c && s != t){
                 in[t] = E[i].c;
                 pre[t] = s;
                 if (s == root){
                     pos = i;
                 } // record the vex whose pre-vex is the vertual root by using the edge's number
             }
         } // find the min-in-arc of every vex
 #ifndef ONLINE_JUDGE
         for (int i = 0; i < v; i++){
             printf("pre %d : %d\n", i, pre[i]);
         }
         printf("root  %d\n", root);
 #endif
         for (int i = 0; i < v; i++){
             vis[i] = -1, fold[i] = -1;
             if (in[i] == inf && i != root) return false;
         } // ensure whether the tree can be build, of course, it is no use in this problem
 
         cnt = 0;
         in[root] = 0;
         for (int i = 0, j, k; i < v; i++){
             if (i == root) continue;
             min_cost += in[i];
             vis[i] = i;
             for (j = pre[i]; vis[j] != i && fold[j] == -1 && j != root; j = pre[j]){
                 vis[j] = i;
             }
             if (j == root || fold[j] != -1) continue;
 
             k = j;
             for (fold[k] = cnt, k = pre[k]; k != j; k = pre[k]) fold[k] = cnt;
             cnt++;
         } // find circle and re-number every vex
 #ifndef ONLINE_JUDGE
         printf("cnt %d\n", cnt);
 #endif
         if (!cnt) return true;
         for (int i = 0; i < v; i++){
             if (fold[i] == -1) fold[i] = cnt++;
         } // re-number the rest single vex
         for (int i = 0; i < e; i++){
             int s = E[i].b;
             int t = E[i].e;
 
             E[i].b = fold[s];
             E[i].e = fold[t];
             if (E[i].b != E[i].e)
                 E[i].c -= in[t];
         } // refresh every arcs
         root = fold[root];
         v = cnt;
     }
 }
 
 
 bool deal(){
     int n, m;
     ll e_sum = 0;
 
     if (scanf("%d%d", &n, &m) == EOF) return false;
     for (int i = 0; i < m; i++){
         scanf("%d%d%I64d", &E[i].b, &E[i].e, &E[i].c);
         E[i].b++; E[i].e++;
         e_sum += E[i].c;
     }
     e_sum++;
     for (int i = 0; i < n; i++){
         E[m + i].b = 0;
         E[m + i].e = i + 1;
         E[m + i].c = e_sum;
     } // build virtual root
     make_tree(0, n + 1, m + n);
     if (min_cost < (e_sum << 1)){
         printf("%I64d %d\n", min_cost - e_sum, pos - m);
     }
     else puts("impossible");
     puts("");
 
     return true;
 }
 
 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
 #endif
     while (deal());
 
     return 0;
 }

 

 

   这是模板的方法,本地的一些比较刁难的数据都能通过,不过就是不知道怎样超时!留着,以后慢慢研究!

#include <cstdio>
 #include <cstring>
 #include <cstdlib>
 #include <cmath>
 #include <algorithm>
 
 #define debug 0
 
 typedef __int64 ll;
 ll max2(ll a, ll b) {return a > b ? a : b; }
 ll min2(ll a, ll b) {return a < b ? a : b; }
 
 const int maxn = 1001;
 const ll inf = 0x7f7f7f7f;
 
 int in[maxn][maxn], out[maxn][maxn];
 //   in-arc          out-arc
 ll cost[maxn][maxn], min_cost;
 ll mf_arc[maxn];
 // min-fold-arc
 int pre[maxn], fold[maxn];
 bool del[maxn], vis[maxn], mk[maxn];
 
 void init(int vn){ // initialize the variable
     for (int i = 0; i <= vn; i++){
         in[i][0] = out[i][0] = 0;
         del[i] = false;
         pre[i] = fold[i] = i;
         mf_arc[i] = inf;
         for (int j = 0; j <= vn; j++){
             cost[i][j] = inf;
         }
     }
 }
 
 void min_tree(int vn, int &rt, int root){
     int i, j, k, cb, t, tmp;
     bool cycle;
 
     #if debug
     for (i = 0; i <= vn; i++){
         for (j = 0; j <= vn; j++){
             if (cost[i][j] == inf) printf("inf ");
             else printf("%3I64d ", cost[i][j]);
         }
         puts("");
     }
     puts("");
     #endif
     min_cost = 0;
     while (true){ // run until no cycles
         cycle = false;
         for (i = 0; i <= vn; i++){
             if (del[i] || i == root) continue;
             cost[i][i] = inf;
             pre[i] = i;
             for (j = 1; j <= in[i][0]; j++){
                 if (del[in[i][j]]) continue;
                 if (cost[pre[i]][i] > cost[in[i][j]][i]){
                     pre[i] = in[i][j];
                 }
             }
         } // find the min-in-arc
         #if debug
         for (i = 1; i <= vn; i++){
             printf("%d : pre  %d   fold  %d\n", i, pre[i], fold[i]);
         }
         puts("");
         #endif
         for (i = 0; i <= vn; i++) vis[i] = false, mk[i] = false;
         for (i = 0; i <= vn; i++){
             if (vis[i] || del[i] || i == root) continue;
             for (j = pre[i]; !vis[j]; vis[j] = true, j = pre[j]);
             cb = j;// suppose cb is cycle-begin
             if (j == root || mk[j]) {
                 mk[i] = true;
                 continue; // if can reach the root, not cycle
             }
             cycle = true;
             #if debug
             printf("when i %d   cycle begin at %d\n", i, cb);
             printf("sub-vexs: ");
             for (j = pre[cb]; j != cb; j = pre[j]) printf("%d ", j);
             puts("");
             #endif
             min_cost += cost[pre[cb]][cb];
             for (j = pre[cb]; j != cb; j = pre[j]){
                 del[j] = true;
                 min_cost += cost[pre[j]][j];
             }
             for (j = 1; j <= in[cb][0]; j++){
                 if (del[in[cb][j]]) continue;
                 cost[in[cb][j]][cb] -= cost[pre[cb]][cb];
                 if (!in[cb][j]){
                     if (mf_arc[cb] > cost[in[cb][j]][cb])
                         fold[cb] = fold[cb], mf_arc[cb] = cost[in[cb][j]][cb];
                     else if (mf_arc[cb] == cost[in[cb][j]][cb])
                         fold[cb] = min2(fold[cb], cb);
                     #if debug
                     printf("mf_arc %d : %I64d    fold %d\n", cb, mf_arc[cb], fold[cb]);
                     #endif
                 }
             }
             cost[pre[cb]][cb] = 0;
             for (j = pre[cb]; j != cb; j = pre[j]){
                 for (k = 1; k <= out[j][0]; k++){
                     t = out[j][k];
                     if (del[t] || t == cb || t == root) continue;
                     if (cost[cb][t] == inf){
                         out[cb][++out[cb][0]] = t;
                         in[t][++in[t][0]] = cb;
                     }
                     cost[cb][t] = min2(cost[cb][t], cost[j][t]);
                 }
                 for (k = 1; k <= in[j][0]; k++){
                     t = in[j][k];
                     if (del[t] || t == cb) continue;
                     if (cost[t][cb] == inf){
                         in[cb][++in[cb][0]] = t;
                         out[t][++out[t][0]] = cb;
                     }
                     tmp = cost[t][j] - cost[pre[j]][j];
                     cost[t][cb] = min2(cost[t][cb], tmp);
                     if (t == root){
                         if (mf_arc[cb] > tmp)
                             fold[cb] = fold[j], mf_arc[cb] = tmp;
                         else if (mf_arc[cb] == tmp)
                             fold[cb] = min2(fold[j], fold[cb]);
                         #if debug
                         printf("sub_mf_arc %d : %I64d    fold %d\n", cb, mf_arc[cb], fold[cb]);
                         #endif
                     }
                 }
                 cost[pre[j]][j] = 0;
             }
             #if debug
             printf("fold %d out %d\n", cb, fold[cb]);
             #endif
             break;
         }
         if (!cycle){
             for (i = 0; i <= vn; i++){
                 if (i == root || del[i]) continue;
                 min_cost += cost[pre[i]][i];
                 if (pre[i] == root) rt = fold[i];
             }
             break;
         }
         #if debug
         printf("vex deleted: ");
         for (i = 0; i <= vn; i++){
             if (del[i]) printf("%d ", i);
         }
         puts("\n");
         printf("min_cost  %I64d\n", min_cost);
         for (i = 0; i <= vn; i++){
             for (j = 0; j <= vn; j++){
                 if (cost[i][j] == inf) printf("inf ");
                 else printf("%3I64d ", cost[i][j]);
             }
             puts("");
         }
         puts("");
         #endif
     }
     #if debug
     printf("min_cost   %I64d\n", min_cost);
     for (i = 0; i <= vn; i++){
         printf("%d : pre  %2d       fold  %2d\n", i, pre[i], fold[i]);
     }
     puts("");
     #endif
 }
 
 
 int main(){
     int n, m;
     int a, b, rt = 0;
     ll c, sum;
 
     while (~scanf("%d%d", &n, &m)){
         init(n);
         sum = 0;
         for (int i = 0; i < m; i++){
             scanf("%d%d%I64d", &a, &b, &c);
             a++; b++;
             sum += c;
             cost[a][b] = min2(cost[a][b], c);
             in[b][++in[b][0]] = a;
             out[a][++out[a][0]] = b;
         }
         sum++;
         #if debug
         printf("sum  %I64d\n", sum);
         #endif
         for (int i = 1; i <= n; i++){
             in[i][++in[i][0]] = 0;
             out[0][++out[0][0]] = i;
             cost[0][i] = sum;
         }
         #if debug
         puts("in-arcs:");
         for (int i = 0; i <= n; i++){
             printf("%d : ", i);
             for (int j = 1; j <= in[i][0]; j++){
                 printf("%d ", in[i][j]);
             }
             puts("");
         }
         puts("");
         #endif
         min_tree(n, rt, 0);
         if (min_cost < (sum << 1)){
             printf("%I64d %d\n", min_cost - sum, rt - 1);
         }
         else{
             puts("impossible");
         }
         puts("");
     }
 
     return 0;
 }

解题转自:http://www.cnblogs.com/LyonLys/archive/2012/08/10/hdu_2121_Lyon.html


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?