【HDU3721】枚举+最长路

题目链接：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=;

 const int oo=0x3fffffff;

 int visit[maxn], pre[*maxn];

 int reach[*maxn], flow[*maxn], head[maxn], next[*maxn];

 int stack[*maxn], sa[*maxn], sb[*maxn];

 int color[*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,,sizeof(visit));

     while(!q.empty()) q.pop();

     Node s, p;

     s.u=ss, s.dis=, s.e=-, sd=-, st=ss;

     q.push(s);

     visit[ss]=;

     int maxx=, pos;

     while(!q.empty())

     {

         p=q.front();

         q.pop();

         for(int i=head[p.u]; i>=; i=next[i])

         {

             if(color[i]||color[i^]) 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]=;

                 pre[s.e]=p.e;

                 if(s.dis>maxx)

                 {

                     st=s.u;

                     maxx=s.dis;

                     sd=s.e;

                 }

                 q.push(s);

             }

         }

     }

     ++op;

     if(op==) bfs(st,op);

     else  ans=maxx;

 }

 int cal(int s[], int n, double len)  ///找最靠近中点的点

 {

     int sum=;

     for(int i=; i<n; i++)

     {

         sum+=flow[s[i]];

         if(sum>=len)

         {

             if(sum-len<=len-(sum-flow[ s[i] ])) return reach[ s[i]^ ];

             else return reach[ s[i] ];

         }

     }

 }

 int Solve(int n)

 {

     int MIN=oo;

     memset(color,,sizeof(color));

     memset(pre,-,sizeof(pre));

     bfs(,);

     int top=;

     while(sd!=-) stack[top++]=sd,sd=pre[sd];

     for(int i=; i<top; i++)  ///枚举最长路上的所有边

     {

         int x=stack[i], na=, nb=;

         color[x]=;

         for(int j=; j<edge; j++) pre[j]=-;

         bfs(reach[x],);

         while(sd!=-) sa[na++]=sd, sd=pre[sd];

         int u=cal(sa,na,1.0*ans/);

         if(!na) u=reach[x];

         for(int j=; j<edge; j++) pre[j]=-;

         bfs(reach[x^],);

         while(sd!=-) sb[nb++]=sd,  sd=pre[sd];

         int v=cal(sb,nb,1.0*ans/);

         if(!nb) v=reach[x^];

         addedge(u,v,flow[x]);

         bfs(,);

         MIN=min(MIN,ans);

         color[edge-]=;    ///注意把新加的边移除，

         color[x]=;

     }

     return MIN;

 }

 int main()

 {

     int n, T, tcase=;

     cin >> T;

     while(T--)

     {

         cin >> n;

         edge=;

         memset(head,-,sizeof(head));

         for(int i=; 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

 */