Note: This article is available in Chinese only. 本文暂无英文版本。
View original
poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 13时03分39秒
4File Name :code/poj/2631.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=1E4+7;
34int n,m;
35vector < pi> edge[N];
36int lst;
37int ans;
38int d[N];
39bool vis[N];
40
41
42void bfs( int s)
43{
44 ms(d,0x3f);
45 ms(vis,false);
46 queue<int>q;
47 q.push(s);
48 vis[s] = true;
49 d[s] = 0 ;
50
51 while (!q.empty())
52 {
53 int u = q.front() ; q.pop();
54 lst = u ;
55// cout<<"u:"<<u<<endl;
56 int siz = edge[u].size();
57
58 for ( int i = 0 ; i < siz ; i++)
59 {
60 int v = edge[u][i].fst;
61 if (vis[v]) continue;
62 vis[v] = true;
63 d[v] = d[u] + edge[u][i].sec;
64 ans = max(d[v],ans);
65 q.push(v);
66 }
67 }
68
69 int mx = 0;
70 for ( int i = 1 ; i <= n ; i++)
71 {
72// cout<<"i:"<<i<<" d[i]:"<<d[i]<<endl;
73 if (d[i]>mx)
74 {
75 mx = d[i];
76 lst = i ;
77 }
78 }
79
80}
81int main()
82{
83 #ifndef ONLINE_JUDGE
84 freopen("code/in.txt","r",stdin);
85 #endif
86
87 int u,v,w;
88 m = 0;
89 n = 0;
90 while (scanf("%d%d%d",&u,&v,&w)!=EOF)
91 {
92 edge[u].push_back(make_pair(v,w));
93 edge[v].push_back(make_pair(u,w));
94 m++;
95 n = max(n,u);
96 n = max(n,v);
97 }
98 ans = inf;
99 bfs(1);
100 ans = 0;
101// cout<<"lst:"<<lst<<endl;
102 bfs(lst);
103 cout<<ans<<endl;
104
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}