文章目录
Cow Marathon
题目链接:http://poj.org/problem?id=1985
题目大意:
有一个颗树,保证无环。现在要求树上结点之间的最大距离。
解题思路:
树的直径
可以随便选择一个点开始进行bfs或者dfs,从而找到离该点最远的那个点(可以证明,离树上任意一点最远的点一定是树的某条直径的两端点之一;树的直径:树上的最长简单路径)。再从找到的点出发,找到据该点的最远点,那么这两点就确定了树的一条直径,两点间距即为所求距离。
using namespace std; struct node { int x, w; }; int n, m, mx = 0, k; vector<node> v[maxn]; int vis[maxn] = {0}; void dfs(int x, int s) { if (s > mx) mx = s, k = x; for (int i = 0; i < v[x].size(); i++) if (!vis[v[x][i].x]) { vis[v[x][i].x] = 1; dfs(v[x][i].x, s + v[x][i].w); vis[v[x][i].x] = 0; } } int main () { while(scanf("%d%d", &n, &m) != EOF) { int x, y; node tmp; char ch; for (int i = 0; i <= n; i++) v[i].clear(); while(m--) { scanf("%d%d%d %c", &x, &y, &tmp.w, &ch); tmp.x = y, v[x].push_back(tmp); tmp.x = x, v[y].push_back(tmp); } mx = 0; mem(vis, 0), vis[1] = 1; dfs(1, 0); mem(vis, 0), vis[k] = 1; dfs(k, 0); cout<<mx<<endl; } return 0; }