「HDU-1520」Anniversary party (树形DP)

发表于 | 分类于 ，

「HDU-1520」Anniversary party
树形DP，树的最大独立集问题

题意

给一颗n个结点的无根树，选出一系列结点，使得在任何两个结点均不相邻的情况下，结点的权值和最大。

解法

树的最大独立集问题。

用$d(i)$表示以$i$为根节点的子树的最大独立集大小。对于结点$i$只有两种决策：选和不选。如果不选$i$,则问题转化成了求出$i$的所有儿子的$d$值再相加；如果选$i$,则它的儿子全部不能选，问题转化为了求出$i$的所有孙子的$d$之和。

状态转移方程为：

$$d(i)=max{\sum_{j∈s(i)}d(j),\sum_{j∈gs(i)}d(j)+val(i)}$$

其中$gs(i)$与$s(i)$分别为$i$的孙子集合与儿子集合。

实现方法：当计算出一个$d(i)$后，用它去更新$i$的父节点和祖父节点。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=6000+10;

vector<int> tree[maxn];
int d[maxn],s[maxn],gs[maxn];
int N,val[maxn];

int dfs(int u,int fa)
{
	for(int i=0;i<tree[u].size();i++)
	{
		int v=tree[u][i];
		if(v!=fa) dfs(v,u);
		s[u]+=d[v];
		if(fa) gs[fa]+=d[v];
	}
	return d[u]=max(s[u],gs[u]+val[u]);
}

int main()
{
	int u,v;
	while(scanf("%d",&N)!=EOF)
	{

		for(int i=1;i<=N;i++)
			scanf("%d",&val[i]);
		for(int i=1;i<=N;i++)
		{
			d[i]=s[i]=gs[i]=0;
			tree[i].clear();
		}
		while(scanf("%d%d",&u,&v)==2&&(u||v))
		{
			tree[u].push_back(v);
			tree[v].push_back(u);
		}
		printf("%d\n",dfs(1,0));
	}
}