转 蓝桥杯 历届试题 大臣的旅费 [ dfs 树的直径 ]

题解：

求树的直径。

转一篇博客：http://www.cnblogs.com/hanyulcf/archive/2010/10/23/tree_radius.html

树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；
              原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
              证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
                      2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
                       所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

相关题目有TOJ1056，TOJ3517.

508294

[e-mail]

大臣的旅费

04-07 20:23

1.113KB

C++

正确

100

0ms

1.238MB

评测详情

代码转自：

http://blog.csdn.net/buctyyzyn/article/details/44886697

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<vector>
 using namespace std;
 #define MAXN 10100

 struct Edge{
     int v,w;
     Edge(int vv,int ww):v(vv),w(ww){}
 };

 int n;
 int dist[MAXN],max_len,End;
 vector<vector<Edge> >G;

 void dfs(int u,int father,int len)
 {
     if(len>max_len)max_len=len,End=u;
     for(int i=;i<G[u].size();i++){
         int v=G[u][i].v,w=G[u][i].w;
         if(v==father)continue;
         dist[v]=max(dist[v],len+w);
         dfs(v,u,len+w);
     }
 }

 int main()
 {
     int u,v,w;
     while(~scanf("%d",&n)){
         G.clear();
         G.resize(n+);
         for(int i=;i<n;i++){
             scanf("%d%d%d",&u,&v,&w);
             G[u].push_back(Edge(v,w));
             G[v].push_back(Edge(u,w));
         }
         memset(dist,,sizeof(dist));
         max_len=;
         dfs(,-,);
         memset(dist,,sizeof(dist));
         max_len=;
         dfs(End,-,);
         int ans=;
         ans=max_len;
        // for(int i=1;i<=n;i++){
         //    ans=max(ans,dist[i]);
        // }
         int tt=;
         for(int i=;i<=ans;i++)
         tt+=(+i);
         printf("%d\n",tt);
     }
     return ;
 }