树的中心

一、定义

到树中其他结点的最远距离最近的结点为树的中心；

二、求法

求出向上最长路与向下最长路后，取两个值得最大值，即为到其他结点的最远距离；

找这个距离最近的点即可；

三、代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 10005
using namespace std;
int n, down1[MAXN], down2[MAXN], up[MAXN], ans = 2147483647;
bool flag[MAXN];
struct edge {
	int to, tot;
};
vector < edge > g[MAXN];
void dfs1(int i) {
	bool f = true;
	flag[i] = true;
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {	
			dfs1(v);
			int ans = down1[v] + tot;
			if (f == true) {
				down1[i] = ans;
				down2[i] = -2147483647;
				f = false;
			} else {
				if (ans > down1[i]) {
					down2[i] = down1[i];
					down1[i] = ans;
				} else {
					down2[i] = max(down2[i], ans);
				}
			}
		
		}
	}
	flag[i] = false;
	return;
}
void dfs2(int i) {]
	flag[i] = true;
	int ans = 0;
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {
			if (down1[i] == down1[v] + tot) {
				ans++;
			}
		}
	}
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {
			up[v] = -2147483647;
			if (down1[i] != down1[v] + tot || (ans > 1 && down1[i] == down1[v] + tot)) {
				up[v] = max(up[v], max(up[i], down1[i]) + tot);
			} else {
				up[v] = max(up[v], max(up[i], down2[i]) + tot);
			}
			dfs2(v);
		}
	}
	return;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		g[y].push_back( edge ( { x, z } ) );
		g[x].push_back( edge ( { y, z } ) );
	}
	dfs1(1);
	dfs2(1);
	for (int i = 1; i <= n; i++) {
		ans = min(ans, max(down1[i], up[i]));
	}
	printf("%d", ans);
	return 0;
}

最后

以上就是优美缘分为你收集整理的树的中心总结树的中心的全部内容，希望文章能够帮你解决树的中心总结树的中心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。