可以证明从树的任意一点出发，所能到达的最远距离一定是树的最大直径的端点。所以两次bfs(),一次任意一点出发，一次端点出发，便能找到最大直径。
程序代码如下：（求树上两端点的最远距离）
#include <iostream> #include <string.h> #define MAXN 10005 #define INF 999999999 using namespace std; struct Edge { int v, w, next; }edge[MAXN]; int head[MAXN], vis[MAXN], d[MAXN], q[MAXN], e, n; int init() { e = 0; memset(head, -1, sizeof(head)); } void add(int u, int v, int w) { edge[e].v = v; edge[e].w = w; edge[e].next = head[u]; head[u] = e++; } void bfs(int src) { for （int i = 0; i <= n; i++) { vis[i] = 0; d[i] = INF; } int h = 0, t = 0; vis[src] = 1; q[t++] = src; d[src] = 0; while (h < t) { int u = q[h++]; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; int w = edge[i].w; if (d[u] + w < d[v]) { d[v] = d[u] + w; if (!vis[v]) { q[t++] = v; vis[v] = 1; } } } } } int main() { int u, v, w; init(); cin >> n; for (int i = 1; i <= n - 1; i++) { cin >> u >> v >> w; add(u, v, w); add(v, u, w); } bfs(1); int pos = 0, mx = -1; for (int i = 1; i <= n; i++) { if(d[i] > mx) { mx = d[i]; pos = i; } } bfs(pos); mx = -1; for (int i = 1; i <= n; i++) { if(d[i] > mx) { mx = d[i]; } } cout << mx << endl; return 0; }
转载于:https://www.cnblogs.com/lihek/p/3216311.html
相关资源：各显卡算力对照表！