XTU 1267 - Highway - [树的直径][2017湘潭邀请赛H题(江苏省赛)]

这道题可能有毒……总之一会儿能过一会儿不能过的，搞的我很心烦……

依然是上次2017江苏省赛的题目，之前期末考试结束了之后有想补一下这道题，当时比较懵逼不知道怎么做……看了题解也不是很懂……就只好放弃了。

后来暑假里学了树形DP，做到了一道有关树的直径的题，把相关方面的知识点算是补了一下，不过当时没想起来这道题目。

今天白天（或者说昨天白天？太晚了233333）学了些有关最大流最小割的东西，想补一下省赛的B题（因为看题解上说的是在网络流……），然而发现题目都有点看不懂，简直不知道发生了什么……正在一脸懵逼的时候，瞟到了这道题，突然发现自己好像可以做了？！？！？！？果断吃过饭，下午开搞……然后磕磕盼盼搞到现在，简直不知道是中了什么毒……embarrassing

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267

Time Limit : 4000 MS Memory Limit : 65536 KB

In ICPCCamp there were n  towns conveniently numbered with 1,2,…,n  connected with (n−1)  roads. The i-th road connecting towns ai and bi has length ci . It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n−1)  highways so that any two towns reach each using only highways. Building a highway between towns x  and y  costs him δ(x,y)  cents, where δ(x,y)  is the length of the shortest path between towns x  and y  using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n−1)  highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n  . The i  -th of the following (n−1)  lines contains three integers a i   , b i   and c i   .

• 1≤n≤10 5
• 1≤a i ,b i ≤n
• 1≤c i ≤10 8
• The number of test cases does not exceed 10  .

Output

For each test case, output an integer which denotes the result.

Sample Input

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

Sample Output

19
15

Source

XTU OnlineJudge

题意：（睡一觉之后再写……）（嗯，早上来补了）题目给你n座城市，n-1条边(包含{u,v,length}三个性质)，然后要一个richman要来建高速路，两座城市间的高速路的造价是这两座城原本的距离；

他想炫富，就要造最贵的n-1条路把这n座城连起来，要求你输出最贵的造价多少。

那我们就想，每座城市肯定最好去连离它最远的那座城市，这样可以保证造价高；

then，我们想到，联想到求树的直径的时候，除了直径的两个端点外，其他的任意点DFS走得最远的那个点就是 one of 直径上的两个点；

那思路就很明确了，求出这棵树的直径，把直径两个端点p1,p2连起来，然后剩下的点，全部连到p1或者p2上（哪个远连哪个），就可以得到题目想要的答案了。

做法是非常暴力的vector邻接表，两次dfs求直径（可以参考http://www.cnblogs.com/dilthey/p/7231438.html），再来一次dfs求距离，最后暴力遍历一遍加一加，搞定。

 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<vector>
 #include<algorithm>
 #define MAXN 100000+5
 #define cls(array,x) memset(array,x,sizeof(array))
 typedef long long ll;
 using namespace std;
 int n,p1,p2;
 struct Edge{
     int u,v;
     ll w;
 };
 vector<Edge> E;
 vector<int> G[MAXN];
 ll d1[MAXN],d2[MAXN],maxd;
 int vis[MAXN];
 void dfs(int now,ll dist,ll d[])
 {
     vis[now]=;
     d[now]=dist;
     for(int i=;i<G[now].size();i++)
     {
         Edge edge=E[G[now][i]];
         int next=edge.v;
         if(!vis[next]) dfs(next,dist+edge.w,d);
     }
 }
 int main()
 {
     while(scanf("%d",&n)!=EOF)
     {
         E.clear();
         for(int i=;i<=n;i++) G[i].clear();
         for(int i=;i<n;i++)
         {
             int from,to,weight;
             scanf("%d%d%d",&from,&to,&weight);
             E.push_back((Edge){from,to,weight});
             G[from].push_back(E.size()-);
             E.push_back((Edge){to,from,weight});
             G[to].push_back(E.size()-);
         }

         cls(vis,);
         dfs(,,d1);
         maxd=;
         for(int i=;i<=n;i++) if(d1[i]>maxd) maxd=d1[i],p1=i;

         cls(vis,);
         dfs(p1,,d1);
         maxd=;
         for(int i=;i<=n;i++) if(d1[i]>maxd) maxd=d1[i],p2=i;

         cls(vis,);
         dfs(p2,,d2);

         ll ans=d1[p2];
         for(int i=;i<=n;i++) if(i!=p1&&i!=p2) ans+=max(d1[i],d2[i]);
         printf("%I64d\n",ans);
     }
     return ;
 }

嗯，总之，过程十分暴力，我喜欢……