poj 1985 Cow Marathon (树的直径模板题)
poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。
思路： **两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；** 原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点 证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度
实际写的时候，第一次bfs最后一个出队的点就是直径的一个端点。。。
好像错了。。。还是稳妥一点。。。最后扫一遍。。距离最远的一定是端点。。。
然后因为题目没有数据范围。。。？re多次orz。。。
/* ***********************************************
Author :111qqz
Created Time :2016年07月12日 星期二 11时26分41秒
File Name :code/poj/1985.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=4E4+5;
7int n,m;
8vector < pi >edge[N];
9int d[N];
10int lst;
11int ans;
12bool vis[N];
1void bfs( int s)
2{
3 ms(vis,false);
4 ms(d,0x3f);
1 queue<int>q;
2 q.push(s);
3 d[s] = 0 ;
4 vis[s] = true;
1 while (!q.empty())
2 {
3 int u = q.front(); q.pop();
4 int siz = edge[u].size();
5 lst = u ;
1 for ( int i = 0 ; i < siz; i++)
2 {
3 int v = edge[u][i].fst;
4 if (vis[v]) continue;
5 vis[v] = true;
6 d[v] = d[u] + edge[u][i].sec;
7 ans = max(ans,d[v]);
8 q.push(v);
9 }
10 }
11 int mx = 0;
12 /* for ( int i = 1 ; i <= n ; i++)
13 {
14 if (d[i]>mx)
15 {
16 mx = d[i];
17 lst = i ;
18 }
19 } */
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6 #endif
7 cin>>n>>m;
8 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
9 for ( int i = 1 ; i <= m ; i++)
10 {
11 int u,v,w;
12 char dir;
13 scanf("%d %d %d %c",&u,&v,&w,&dir); //dir这东西有用？
14 edge[u].push_back(make_pair(v,w));
15 edge[v].push_back(make_pair(u,w));
16 }
1 ans = inf;
2 bfs(1);
3 ans = 0;
4// cout<<"lst:"<<lst<<endl;
5 bfs(lst);
6 cout<<ans<<endl;
7 #ifndef ONLINE_JUDGE
8 fclose(stdin);
9 #endif
10 return 0;
11}