POJ 1985 Cow Marathon（树的直径模板）

http://poj.org/problem?id=1985

题意：
给出树，求最远距离。

题意：

树的直径。

树的直径是指树的最长简单路。

求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径。

原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点。
证明:
1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 using namespace std;
11 
12 const int maxn=1e5+5;
13 
14 typedef pair<int, int> pll;
15 int n,m;
16 int d[maxn];
17 vector<pll> edge[maxn];
18 
19 int bfs(int u)
20 {
21     queue<int> Q;
22     Q.push(u);
23     d[u]=0;
24     int max_d=0,max_u=u;
25     while(!Q.empty())
26     {
27         u=Q.front(); Q.pop();
28         if(d[u]>max_d)  {max_d=d[u];max_u=u;}
29         for(int i=0;i<edge[u].size();i++)
30         {
31             int v=edge[u][i].first;
32             if(d[v]==-1)
33             {
34                 Q.push(v);
35                 d[v]=d[u]+edge[u][i].second;
36             }
37         }
38     }
39     return max_u;
40 }
41 
42 int main()
43 {
44     //freopen("D:\input.txt","r",stdin);
45     while(~scanf("%d%d",&n,&m))
46     {
47         int u,v,w; char c;
48         for(int i=1;i<=n;i++)  edge[i].clear();
49         while(m--)
50         {
51             scanf("%d%d%d%c%c",&u,&v,&w,&c,&c);
52             edge[u].push_back(make_pair(v,w));
53             edge[v].push_back(make_pair(u,w));
54         }
55         memset(d,-1,sizeof(d));
56         int p=bfs(1);
57         memset(d,-1,sizeof(d));
58         int q=bfs(p);
59         int ans=d[q];
60         printf("%d
",ans);
61     }
62     return 0;
63 }