poj 2631 Roads in the North 树的直径之树形DP求法

缘起

【1】和【2】分别给出了树的直径的bfs、dfs求法. 但是紫书P434还给出了树形DP的解法. 遂找道题目来学习一下~ poj 2631 Roads in the North

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给你一棵顶点1w的无根树, 要你求树的直径. 

【输入】
本题只需处理一组数据. 有若干行, 每行包含三个正整数, a,b,c(a!=b)表明a和b之间的无向边的长度是c

【输出】
树的直径

【样例输入】
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

【样例输出】
22

【限制】
1s

关于树的直径的树形DP解法在紫书中就有论述, 首先, 随便取一个根（例如1）.使之成为有根树 然后

令d[i] 是顶点i到达它对应子树中的叶子中的最大长度. 则 d[i] = max{d[j]+dis(i,j)}, 通过树形dp将所有点的dp值求出来之后， 令d[i]、d[j] 是根节点的诸多子节点的d值中的排名前2(当然, 前提是根节点有>1个子节点)的. 则 d[i]+d[j]就是答案。

而树形dp的过程完全可以放到dfs中去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int d[maxn];
struct kk
{
	int to, len;
	kk(int to, int len):to(to),len(len){}
	bool operator <(kk &o)
	{
		return d[to]+len>d[o.to]+o.len; // 按照距离的值降序排序
	}
};
vector<kk> g[maxn];
typedef vector<kk>::iterator vit;


void dfs(int cur, int fa)
{
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (x->to==fa)
		{
			continue;
		}
		dfs(x->to, cur);
		d[cur] = max(d[cur], d[x->to]+x->len);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	int a,b,c, inf = 0x3f3f3f3f;
	while(~scanf("%d%d%d", &a,&b,&c))
	{
		g[a].push_back(kk(b,c));
		g[b].push_back(kk(a,c));
	}
	dfs(1,0);
	sort(g[1].begin(), g[1].end());
	int ans = 0;
	if (g[1].size()>0) // 要考虑根节点只有1个子节点的情况
	{
		ans += g[1][0].len+d[g[1][0].to];
	}
	if (g[1].size()>1)
	{
		ans+=g[1][1].len+d[g[1][1].to];
	}
	printf("%d", ans);
	return 0;
}

ac情况

Status Accepted
Time 47ms
Memory 536kB
Length 990
Lang C++
Submitted 2019-11-06 19:14:43
Shared
RemoteRunId 21027480

参考

【1】https://yfsyfs.github.io/2019/09/10/poj-1985-Cow-Marathon-%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/

【2】https://yfsyfs.github.io/2019/09/10/hdu-2196-Computer-%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/