本文主要是介绍POJ2631 : Roads in the North，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：嘤嘤嘤
题目大意：给你一个无向带权树，让你求最长路径（树的直径）
解题思路：任选一个点，用dfs跑一遍，记录与这个点最远的点s，再从s点dfs一遍，即可求得直径。
数据给的 n <= 1e4,然而枚举每一个点都用dfs跑一遍居然也能过...这题数据有点水。
证明如下：
这里给出树的直径的证明：
主要是利用了反证法：
假设 s-t这条路径为树的直径，或者称为树上的最长路
现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍dfs就可以找出树的最长路。
证明：
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矛盾
就不贴原文链接了，相同的太多，也不知道谁是真的作者。（反正不是我写的）
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FAST ios::sync_with_stdio(false)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
using namespace std;vector< pair<int, int> > vec[maxn];
int dis[maxn];
bool vis[maxn];
int ans, S;void DFS(int u)
{vis[u] = true;if(dis[u] > ans){ans = dis[u];S = u;}int Size = vec[u].size();for(int i = 0; i < Size; i++){int v = vec[u][i].first;int w = vec[u][i].second;if(!vis[v]){dis[v] = dis[u] + w;DFS(v);}}
}int main()
{int u, v, w;while(~scanf("%d %d %d", &u, &v, &w)){vec[u].push_back(make_pair(v, w));vec[v].push_back(make_pair(u, w));}ans = 0;DFS(1);memset(vis, false, sizeof(vis));ans = 0;memset(dis, 0, sizeof(dis));DFS(S);printf("%d\n", ans);return 0;
}学会了pair很开心
over.
这篇关于POJ2631 : Roads in the North的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
