最长网线

问题描述

实验室里原先有一台电脑(编号为 1 )，最近又购置了 N - 1 台电脑，编号为 2 到 N 。每台电脑都用网线连接到一台先前安装的电脑上。求第 i 台电脑到其他电脑的最大网线长度。

Input

输入文件包含多组测试数据。对于每组测试数据，第一行一个整数 N (N ≤ 10000)，接下来有 N - 1 行，每一行两个数，对于第 j 行的两个数，它们表示与 i 号电脑连接的电脑编号以及它们之间网线的长度。网线的总长度不会超过 10^9，每个数之间用一个空格隔开。

Output

对于每组测试数据输出 N 行，第 i 行表示 i 号电脑的答案 (1 ≤ i ≤ N).

Sample

Input: 
5
1 1
2 1
3 1
1 1

Output: 
3
2
3
4
4

Limitation

Time limit		1000 ms
Memory limit	32768 kB

解题思路

每台电脑最多有2条网线相连，因此可以看成一棵树，采用邻接矩阵来储存节点。

利用DFS逐个求出每个节点的最长路径会超时，但是本题连接的网线可以看成一棵没有分支的树，是一条链，树的直径就是链长，因此可以求出链的两端点到每个节点的距离，更新最大距离即可。

树的直径：从某个点开始遍历，它能到达的终点就是直径的一个端点；再从这个得到的端点开始遍历，它能到达的终点就是直径的另一个端点。

本题进行3次DFS就能得出结果。

源代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory>
using namespace std;

const int maxN = 10005;

struct edge {
	int v;
	long long w;
	edge() { v = 0; w = 0; }
	edge(int _v, long long _w) :v(_v), w(_w) {  }
};

vector<edge> edges[maxN];
bool visit[maxN];
long long path[maxN];
int source;//直径的端点

void dfs(int s, long long length) {
	visit[s] = true;
	for (int i = 0; i < edges[s].size(); i++) {
		int temp = edges[s].at(i).v;
		long long tempW = edges[s].at(i).w;
		if (!visit[temp]) {
			path[temp] = max(path[temp], length + tempW);
			if (path[source] < path[temp])
				source = temp;
			dfs(temp, length + tempW);
		}
	}
}

void thePath(int n) {
	source = 1;
	memset(visit, false, sizeof(visit));
	memset(path, 0, sizeof(path));

	dfs(1, 0);//第一次 从第一个点开始 求得直径的一个端点

	memset(visit, false, sizeof(visit));
	dfs(source, 0);//第二次 从求得的端点开始 求得另一端点 同时更新最长路径

	memset(visit, false, sizeof(visit));
	dfs(source, 0);//第三次 从上一次求得的端点开始 更新最长路径
	for (int i = 1; i <= n; i++)
		printf("%lld\n", path[i]);
}

int main() {
	int n;
	while (scanf_s("%d", &n) != EOF) {
		for (int i = 2; i <= n; i++) {
			int a;
			long long b;
			scanf_s("%d %lld", &a, &b);
			edge e1(a, b);
			edge e2(i, b);
			edges[i].push_back(e1);
			edges[a].push_back(e2);
		}
		thePath(n);
		for (int i = 0; i <= n; i++)
			edges[i].clear();
	}

	return 0;
}