题目：http://www.lightoj.com/volume_showproblem.php?problem=1094
题意：给定一个由n个点的树，树边都有权值，求树中相距最远的两个点的距离是多少
思路：此题求树的直径。首先任选一点做dfs，求出此点到其他点的距离，然后从距离最远的点（此点为树的直径的一个端点）开始再做一次dfs，求出到所有点的距离，此时的最大距离就是树上两点间的最大距离，也就是树的直径。证明网上一大堆
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <queue> #include <map> using namespace std; const int N = 30010, INF = 0x3f3f3f3f; struct edge { int to, cost, next; }g[N*2]; int cnt, head[N]; bool vis[N]; int dep[N]; int n, cas, res; void add_edge(int v, int u, int cost) { g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++; } void dfs(int v, int d) { vis[v] = true, dep[v] = d; if(dep[v] > dep[res]) res = v;//记录距离最大的那个点 for(int i = head[v]; i != -1; i = g[i].next) { int u = g[i].to; if(! vis[u]) dfs(u, dep[v] + g[i].cost); } } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d", &n); int v, u, c; cnt = 0; memset(head, -1, sizeof head); for(int i = 1; i <= n - 1; i++) { scanf("%d%d%d", &v, &u, &c); add_edge(v, u, c), add_edge(u, v, c); } memset(vis, 0, sizeof vis); res = 0; dfs(0, 0); memset(vis, 0, sizeof vis); dfs(res, 0); printf("Case %d: %d\n", ++cas, dep[res]); } return 0; }