树的中心(树形动态规划)

63 阅读 0 评论 42 点赞

我是靠谱客的博主魔幻小白菜，最近开发中收集的这篇文章主要介绍树的中心(树形动态规划)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

树的中心

问题描述

给一棵树，树中包含 n 个结点（编号1~n）和 n−1条无向边，每条边都有一个权值。请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。
输入格式
第一行包含整数 n。
接下来 n−1行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci的边。
输出格式
输出一个整数，表示所求点到树中其他结点的最远距离。
数据范围
1≤n≤10000,1≤ai,bi≤n,1≤ci≤10⁵
输入样例：
6
2 1 3
3 4 2
3 2 1
6 5 2
5 2 1
输出样例：
3

问题分析

树的中心一定位于树的直径上。
此题描叙的是无根树，求解时可以按照有根树的思路来分析。
每个节点可以向下走（多叉），亦可以向上走（一叉，因为是树）。
叶子节点无向下走的路径，根节点（任意指定）无向上的路径。
某节点向下的路径和向上的路径长度取个最大值，即为该点到其余各点的最大距离，求得所有节点的最大距离，再取个最小值即可。
实现：　树上动态规划，两遍DFS

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//树的中心
//DFS

using namespace std;
const int  N = 10007
const int  M = 20017;
const int INF = 0x3f3f3f3f; 

int n;
int h[N], e[M], w[M] , ne[M], cnt;
int down1[N], down2[N], up[N];//向下的最长，次长路径
                              //up记录向上访问的最长路径
int p1[N]; 

void add(int a, int b, int c)
{
	e[cnt] = b, w[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
}

int  dfs_d(int u, int parent)
{
	down1[u] = down2[u] = -INF;
	
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(j == parent) continue;
		int d = dfs_d(j, u) + w[i];
		if(d >= down1[u]) 
		{
			down2[u] = down1[u], down1[u] = d;
			p1[u] = j;//save position
		}
		else if(d > down2[u]) down2[u] = d;
	}
	if(down1[u]==-INF) down1[u]=down2[u]=0;//leaf
	
	return down1[u]; 
}

void dfs_u(int u ,int parent)
{
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(j == parent) continue;
		
		if(p1[u] == j) up[j] = max(up[u],down2[u]) + w[i];
		else up[j] = max(up[u],down1[u]) + w[i];
		
		dfs_u(j, u);
	}
}
int main()
{
	cin >> n;
	memset(h, -1,sizeof h);
	for(int i = 0; i <= n-2; i ++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b,a, c);
	}
	
	dfs_d(1, -3);//向下访问
    dfs_u(1, -3);//向上访问
    
    int res = INF;
    for(int i = 1; i <= n; i ++) 
      res = min(res,  max(down1[i],up[i]));   
    cout << res  << endl;
    
  return 0;
}