POJ 2631 Roads in the North

Description

Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.

The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.

Input

Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.

Output

You are to output a single integer: the road distance between the two most remote villages in the area.

Sample Input

Sample Output

传送门：

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

题意：

输入起点、终点和两点的权值，求出这个树的直径。

树的直径的证明：

（主要是利用了反证法）
　　假设 s-t这条路径为树的直径，或者称为树上的最长路现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后再从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路
证明：

　　1.设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则 dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾

　　2.设u不为s-t路径上的点首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了，

所以现在又有两种情况了：

　　1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)

　　2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾

思路：

随便找一个点a进行dfs搜索，得到一个b点（距离a点最远的点），然后再从b点dfs搜索，就得到树的直径了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 const int maxn = 91000;
 6 struct node
 7 {
 8     int to;
 9     int w;
10     int next;
11 };
12 node edges[maxn << 1];
13 int head[maxn << 1];
14 bool vis[maxn];
15 int tot;
16 int ans;
17 int p;
18 void add_edges(int u, int v, int w)
19 {
20     edges[++tot].to = v;
21     edges[tot].w = w;
22     edges[tot].next = head[u];
23     head[u] = tot;
24 }
25 void dfs(int root, int sum)
26 {
27     bool flag = true;
28     vis[root] = true;
29     for(int i = head[root]; i; i = edges[i].next)
30     {
31         int v = edges[i].to;
32         if(!vis[v])
33         {
34             flag = false;
35             dfs(v, sum + edges[i].w);
36         }
37     }
38     if(flag)
39     {
40         if(sum > ans)
41         {
42             ans = sum;
43             p = root;
44         }
45     }
46 }
47 int main()
48 {
49     memset(head, 0, sizeof(head));
50     int a, b, c;
51     while(scanf("%d%d%d", &a, &b, &c) != EOF)
52     {
53         add_edges(a, b, c);
54         add_edges(b, a, c);
55     }
56     memset(vis, false, sizeof(vis));
57     dfs(1, 0);
58     memset(vis, false, sizeof(vis));
59     dfs(p, 0);
60     cout << ans << endl;
61 }