Description Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes. Input Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree. Output For each case, print the case number and the maximum distance. Sample Input 2 4 0 1 20 1 2 30 2 3 50 5 0 2 20 2 1 10 0 3 29 0 4 50 Sample Output Case 1: 100 Case 2: 80 Source Problem Setter: Jane Alam Jan |  |
今天又学了一个数据结构，用来存储树和图的，叫做前向星。
struct node{ int from; //该条边的起点 int to; //该条边的终点 int val; //该条边的权值 int next; //该条边的起点所连接的下一条边} edge[MAXN]; 对于图或者树的储存
//储存一个起点为x， 终点为y，权值为z的边。//edgenum为边的计数。void addedge(int x, int y, int z) { edge[edgenum].from = x; edge[edgenum].to = y; edge[edgenum].val = z; edge[edgenum].next = head[x]; //把属于x的边的最后一个的“地址”赋予head[x] head[x] = edgenum++;} 在遍历树的时候，从i节点开始，head[i]中存放着i节点最后一个边的“地址”，edge[head[i]].next指向的就是i节点的下一个，依次进行遍历。
#include#define MAXN 30010using namespace std;struct node{ int from, to, val, next;} edge[MAXN];bool vis[MAXN];int dist[MAXN], head[MAXN], edgenum, ans, s;void init() { memset(head, -1, sizeof(head)); edgenum = 0;}void addedge(int x, int y, int z) { edge[edgenum].from = x; edge[edgenum].to = y; edge[edgenum].val = z; edge[edgenum].next = head[x]; head[x] = edgenum++;}void bfs(int x) { queue que; ans = 0; memset(vis, false, sizeof(vis)); memset(dist, 0, sizeof(dist)); while (!que.empty()) que.pop(); que.push(x); vis[x] = true; while (que.size()) { int a = que.front(); que.pop(); for (int i = head[a]; i != -1; i = edge[i].next) { int b = edge[i].to; if (!vis[b] && dist[b] < dist[a] + edge[i].val) { dist[b] = dist[a] + edge[i].val; if(ans < dist[b]) { ans = dist[b]; s = b; } vis[b] = true; que.push(b); } } }}int main() { int t, a, b, c, n; int cnt = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); init(); for (int i = 0; i < n-1; i++) { scanf("%d%d%d", &a, &b, &c); addedge(a, b, c); addedge(b, a, c); } bfs(0); bfs(s); printf("Case %d: %d\n", ++cnt, ans); } return 0;}