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.
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 ai , bi and ci .
1≤n≤105 1≤ai,bi≤n 1≤ci≤108 The number of test cases does not exceed 10 .For each test case, output an integer which denotes the result.
原题链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267
题意：n个城镇之间有n-1条道路相连，现在有个有钱人要来修n-1条高速公路，使得任意两个城镇之间都有唯一的高速公路，问你最多要花费多少钱。
对于样例1：
最远的两个点为4和5
对于1，从1修到4，花费4
对于2，从2修到5，花费4
对于3，从3修到4，花费5
对于4，从4修到5，花费6
对于5，从5修到4，花费6
从4到5和从5到4是一样的，算一次即可。
最终花费为4+4+5+6=19
对于此题，要用到树的直径，输的直径就是一棵树上最远的两个节点。
找到输的直径后，树上的点到直径上的两个端点(必为其中一个)的距离最远。
求直径的过程中就可以与处理处每个节点到端点的最短距离。
最后再遍历每个节点，找到最大的再相加就可以了。
AC代码1
参考博客：http://blog.csdn.net/WuBaizhe/article/details/72615543
设直径两个端点分别是 rt_1 和 rt_2 代码的思路是先从1节点搜索到距离最远的直径上的节点rt_1，然后再从rt_1搜索找到距其最远的节点rt_2，同时更新每一个点到rt_1的距离，再从rt_2进行搜索更新每一个点到直径节点的距离，然后每个点到直径节点的最大距离进行累加。因直径考虑了两次，故减去一次直径就是最后的答案，三次搜索即可。
AC代码:
/** * 行有余力，则来刷题！ * 博客链接:http://blog.csdn.net/hurmishine * */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e5+5; typedef long long LL; struct Node { int v,next; LL w; }edge[maxn<<1]; LL dis[maxn]; LL DIS;//树的直径 int head[maxn]; int cnt; bool vis[maxn]; int n; int root1,root2; void addEdge(int u,int v,LL w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } //求树的直径, //u-起点,d-距离 void DFS1(int u, LL d) { vis[u]=true; if(d>DIS) { DIS=d; root1=u; } for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].v; LL w = edge[i].w; if(!vis[v]) { DFS1(v,d+w); } } } void DFS2(int u,LL d ,bool type) { vis[u]=true; dis[u]=max(dis[u],d); if(type&&d>DIS) { root2=u; DIS=d; } for(int i=head[u];~i;i=edge[i].next) { int v = edge[i].v; LL w = edge[i].w; if(!vis[v]) { DFS2(v,d+w,type); } } } void solve() { root1=root2=0; memset(vis,false,sizeof(vis)); DIS=0; DFS1(1,0); memset(dis,0,sizeof(dis)); memset(vis,false,sizeof(vis)); DIS=0; DFS2(root1,0,true); memset(vis,false,sizeof(vis)); DFS2(root2,0,false); LL ans=0; dis[root1]=0; //cout<<root1<<","<<root2<<endl; for(int i=1;i<=n;i++) { ans += dis[i]; } cout<<ans<<endl; } int main() { //freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt","r",stdin); while(cin>>n) { memset(head,-1,sizeof(head)); cnt=0; int u,v; LL w; for(int i=1;i<n;i++) { //cin>>u>>v>>w; scanf("%d%d%I64d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } solve(); } return 0; } AC代码2:
参考博客:http://www.cnblogs.com/fightfordream/p/6860903.html
只用了一个DFS,但是每次搜索的时候都要把根节点传递进去,我用了vis来标记,搜索减少了一个参数.
/** * 行有余力，则来刷题！ * 博客链接:http://blog.csdn.net/hurmishine * */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=1e5+5; typedef long long LL; struct Edge { int v,next; LL w; Edge() {} Edge(int v,int next,LL w):v(v),next(next),w(w) {} } edge[maxn<<1]; LL dis[2][maxn]; int n; int cnt; int head[maxn]; bool vis[maxn]; int p;//记录直径端点 LL D;//树的直径 void addEdge(int u,int v,LL w) { edge[cnt]=Edge(v,head[u],w); head[u]=cnt++; } void DFS(int u,int k) { vis[u]=true; if(dis[k][u] > D) { p = u; D = dis[k][u]; } for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; //注意此处标记的是v而不是i !!!!! if(!vis[v]) { vis[v]=true; dis[k][v] = edge[i].w + dis[k][u]; DFS(v, k); } } } int main() { //freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt","r",stdin); while(cin>>n) { memset(head,-1,sizeof(head)); cnt=0; int u,v; LL w; for(int i=1; i<n; i++) { scanf("%d%d%I64d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } memset(vis,false,sizeof(vis)); memset(dis,0,sizeof(dis)); //从1开始,找树的直径的一个端点r1 dis[0][1]=0; D=0; DFS(1,0); int r1=p;//r1为一个端点 //从r1开始,找树的直径的另一个端点r2 //并记录r1到每个点的最短距离dis[0][] memset(vis,false,sizeof(vis)); dis[0][r1]=0; D=0; DFS(r1,0); int r2=p; //求r2到每个点的最短距离dis[1][] memset(vis,false,sizeof(vis)); dis[1][r2]=0; DFS(r2,1); //cout<<r1<<","<<r2<<endl; //遍历每个节点,求出到直径端点的最大值 LL ans=0; for(int i=1; i<=n; i++) { ans+=max(dis[0][i],dis[1][i]); } //树的直径加了两次 cout<<ans-D<<endl; //cout<<ans-dis[1][r1]<<endl; //cout<<ans-dis[0][r2]<<endl; } return 0; }
