Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 11时26分41秒
4File Name :code/poj/1985.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=4E4+5;
34int n,m;
35vector < pi >edge[N];
36int d[N];
37int lst;
38int ans;
39bool vis[N];
40
41void bfs( int s)
42{
43 ms(vis,false);
44 ms(d,0x3f);
45
46 queue<int>q;
47 q.push(s);
48 d[s] = 0 ;
49 vis[s] = true;
50
51 while (!q.empty())
52 {
53 int u = q.front(); q.pop();
54 int siz = edge[u].size();
55 lst = u ;
56
57 for ( int i = 0 ; i < siz; i++)
58 {
59 int v = edge[u][i].fst;
60 if (vis[v]) continue;
61 vis[v] = true;
62 d[v] = d[u] + edge[u][i].sec;
63 ans = max(ans,d[v]);
64 q.push(v);
65 }
66 }
67 int mx = 0;
68 /* for ( int i = 1 ; i <= n ; i++)
69 {
70 if (d[i]>mx)
71 {
72 mx = d[i];
73 lst = i ;
74 }
75 } */
76
77}
78int main()
79{
80 #ifndef ONLINE_JUDGE
81 freopen("code/in.txt","r",stdin);
82 #endif
83 cin>>n>>m;
84 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
85 for ( int i = 1 ; i <= m ; i++)
86 {
87 int u,v,w;
88 char dir;
89 scanf("%d %d %d %c",&u,&v,&w,&dir); //dir这东西有用？
90 edge[u].push_back(make_pair(v,w));
91 edge[v].push_back(make_pair(u,w));
92 }
93
94 ans = inf;
95 bfs(1);
96 ans = 0;
97// cout<<"lst:"<<lst<<endl;
98 bfs(lst);
99 cout<<ans<<endl;
100 #ifndef ONLINE_JUDGE
101 fclose(stdin);
102 #endif
103 return 0;
104}