首页 > 搜索 > BFS搜索 > HDU 3721-Building Roads-图-[解题报告]HOJ
2015
02-21

HDU 3721-Building Roads-图-[解题报告]HOJ

Building Roads

问题描述 :

There is a magic planet in the space. There is a magical country on the planet. There are N cities in the country. The country is magical because there are exactly N-1 magic roads between the N cities, and from each city, it is possible to visit any other city. But after the huge expansion of the country, the road system seems to be messy. The moderator decided to rebuild the road system.

As a worker, I cannot do too much things. I could just move one road to another position connecting arbitrary 2 cities using my magic, keeping its length unchanged. Of course, afterwards all the N cities have to be still connected. I wonder how to move in order to make the farthest distance between any two cities minimum. Could you solve it for me?

输入:

The first line of the input is one integer T (T ≤ 10), and then T test cases follow.
Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.
Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

输出:

The first line of the input is one integer T (T ≤ 10), and then T test cases follow.
Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.
Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

样例输入:

2
4
0 1 2
1 2 2
2 3 2
5
0 1 1
1 2 2
2 3 3
3 4 4

样例输出:

Case 1: 4
Case 2: 7

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3721

 

题意:给你一颗n个节点n-1条边的树,每条边都有一个权值,现在让你任意移动一条边然后把这条边连接到任意两个点上,最后问你怎样移动才能使树上相距最远的两个点距离最小。

 

思路:先求出树的最长路,然后枚举移动最长路上的所有边,移走这条边后,原树必定分为不连接的两颗子树,分别求这两颗子树的最长路,然后分别找到两颗子树最长路上靠近中点的点,把这两个点连上刚刚从母树移走的边,再求一遍母树最长路,比较所有结果取最优解即可。

注意每次枚举移动后都要把图复原然后继续枚举。

 

 #pragma comment(linker, "/STACK:1024000000,1024000000")
 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <queue>
 #include <algorithm>
 using namespace std;
 
 const int maxn=2555;
 const int oo=0x3fffffff;
 int visit[maxn], pre[10*maxn];
 int reach[10*maxn], flow[10*maxn], head[maxn], next[10*maxn];
 int stack[10*maxn], sa[10*maxn], sb[10*maxn];
 int color[10*maxn];
 int st, sd, ans, edge;
 
 struct Node
 {
     int u, e;
     int dis;
 };
 queue<Node>q;
 
 inline void addedge(int u, int v, int c)
 {
     reach[edge]=v, flow[edge]=c, next[edge]=head[u], head[u]=edge++;
     reach[edge]=u, flow[edge]=c, next[edge]=head[v], head[v]=edge++;
 }
 
 void bfs(int ss,int op)
 {
     memset(visit,0,sizeof(visit));
     while(!q.empty()) q.pop();
     Node s, p;
     s.u=ss, s.dis=0, s.e=-1, sd=-1, st=ss;
     q.push(s);
     visit[ss]=1;
     int maxx=0, pos;
     while(!q.empty())
     {
         p=q.front();
         q.pop();
         for(int i=head[p.u]; i>=0; i=next[i])
         {
             if(color[i]||color[i^1]) continue;
             int v=reach[i], val=flow[i];
             s.u=v, s.dis=p.dis+val, s.e=i;
             if(!visit[s.u])
             {
                 visit[s.u]=1;
                 pre[s.e]=p.e;
                 if(s.dis>maxx)
                 {
                     st=s.u;
                     maxx=s.dis;
                     sd=s.e;
                 }
                 q.push(s);
             }
         }
     }
     ++op;
     if(op==1) bfs(st,op);
     else  ans=maxx;
 }
 
 int cal(int s[], int n, double len)  ///找最靠近中点的点
 {
     int sum=0;
     for(int i=0; i<n; i++)
     {
         sum+=flow[s[i]];
         if(sum>=len)
         {
             if(sum-len<=len-(sum-flow[ s[i] ])) return reach[ s[i]^1 ];
             else return reach[ s[i] ];
         }
     }
 }
 
 int Solve(int n)
 {
     int MIN=oo;
     memset(color,0,sizeof(color));
     memset(pre,-1,sizeof(pre));
     bfs(1,0);
     int top=0;
     while(sd!=-1) stack[top++]=sd,sd=pre[sd];
     for(int i=0; i<top; i++)  ///枚举最长路上的所有边
     {
         int x=stack[i], na=0, nb=0;
         color[x]=1;
         for(int j=0; j<edge; j++) pre[j]=-1;
         bfs(reach[x],0);
         while(sd!=-1) sa[na++]=sd, sd=pre[sd];
         int u=cal(sa,na,1.0*ans/2);
         if(!na) u=reach[x];
         for(int j=0; j<edge; j++) pre[j]=-1;
         bfs(reach[x^1],0);
         while(sd!=-1) sb[nb++]=sd,  sd=pre[sd];
         int v=cal(sb,nb,1.0*ans/2);
         if(!nb) v=reach[x^1];
         addedge(u,v,flow[x]);
         bfs(1,0);
         MIN=min(MIN,ans);
         color[edge-1]=1;    ///注意把新加的边移除,
         color[x]=0;
     }
     return MIN;
 }
 
 int main()
 {
     int n, T, tcase=0;
     cin >> T;
     while(T--)
     {
         cin >> n;
         edge=0;
         memset(head,-1,sizeof(head));
         for(int i=1; i<n; i++)
         {
             int a, b, c;
             scanf("%d%d%d",&a,&b,&c);
             addedge(a,b,c);
         }
         int tmp=Solve(n);
         printf("Case %d: %d\n",++tcase,tmp);
     }
 }
 /*
 10
 9
 0 1 1
 1 2 1
 2 3 1
 2 4 1
 0 5 1
 5 6 1
 5 7 1
 7 8 1
 4
 0 1 2
 1 2 2
 2 3 2
 5
 0 1 1
 1 2 2
 2 3 3
 3 4 4
 */

 

参考:http://www.cnblogs.com/kane0526/archive/2013/09/09/3310915.html


, ,
  1. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  2. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  3. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  4. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  5. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  6. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  7. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  8. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  9. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  10. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  11. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  12. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  13. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  14. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  15. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  16. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  17. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  18. 世界灵异事件之一,漫步的孩子。晚上1***点1***分,楼房角落可以看见一个原地踏步走的孩子,看不见他的脸,如果没将这消息传五个帖子,将家破人亡,被那个***于非命的孩子夺取心脏。对不起了,我也是无意中看到的,我不想失去家人,所以只能发了。抱歉世界灵异事

  19. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  20. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  21. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  22. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  23. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?