uva 1220 Party at Hali-Bula 树的最大独立集+判重

缘起

此题是紫书上的一道树形DP题 ~ uva 1220 Party at Hali-Bula

分析

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
公司里有n（n≤200）个人形成一个树状结构，即除了boss之外每个员工都有唯一的直属上司。 
要求选尽量多的人，但不能同时选择一个人和他的直属上司。 
问：最多能选多少人，以及在人数最多的前提下方案是否唯一

【输入】
多样例. 每个样开始于n, 然后下一行是大boss(即根节点)的名字, 然后n-1行每行2个名字, 分别是下属和它的
直接领导. 每个名字至少一个字符,至多100个字符.每个样例以0结束.

【输出】
对每个样例输出最多能邀请的人数, 以及此方案是否唯一.

【样例输入】
6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0

【样例输出】
4 Yes
1 No

【限制】
3s

这是紫书P434上介绍的树的最大独立集问题. 即

1
2
树的最大独立集。 对于一棵n个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集），
然后输入n-1条无向边，输出一个最大独立集（如果有多解，则任意输出一组）。

如果仅仅是计算最大独立集的元素个数的话, 紫书 P434 已经给出了答案. 即用d(i)表示以i为根结点的子树的最大独立集大小。 则根据选与不选顶点i， 可以得到如下dp方程

其中，gs(i)和s(i)分别为i的孙子节点集合与儿子节点集合. 只需要知道如果选了i的话, 它的子节点就都不能选, 而只能选它的孙子节点, 则上面的dp公式就很好理解.

但是上面的公式其实是不利于树形dp的. 因为树形DP本质就是dfs. 所以转而要使用紫书P434 上面谈到的刷表法而不是dp一贯的填表法. 刷表法其实就是我在插头DP文章中用的dp过程，其实刷表就是更新. 填表就是一锤定音.

刷表法的话, 就要类似于拓扑排序. 虽然能做，但是都不是更好的技巧.更好的技巧是双状态dp （唉，只能说一句，dp博大精深！）

1
2
3
4
5
6
令 
d[i][0] = 以i为根节点的子树不选i的最大独立集的元素个数。
d[i][1] = 以i为根节点的子树选i的最大独立集的元素个数。
则
d[i][1] = 1+\Sigma_{j是i的子节点}d[j][0]
d[i][0] = \Sigma_{j是i的子节点}max(d[j][0], d[j][1]), 注意,因为i没有选, 所以j可选可不选

则显然最后整棵树最大独立集的个数是max{d[root][0], d[root][1]}

wait~ wait~ wait

本题还要考虑唯一性. 这本质上也是一个状态. 和上面考虑的d表示元素数量没有什么不同之处，我们完全可以效仿上面再令一个新的状态出来.

1
2
3
4
5
6
7
f[i][0]表示以i为根节点的子树, 达到d[i][0]时是否唯一.取值为true或者false
f[i][1]表示以i为根节点的子树, 达到d[i][1]时是否唯一.取值为true或者false
则
f[i][0] = true当且仅当f[j][1]都是true才行, 其中j是i的所有子节点. 
f[i][1]的话, 稍微复杂一些. 什么时候f[i][1]=true呢? 首先，如果某个d(j,0)和d(j,1)相等，则肯定
不唯一；其次，如果max取到的那个值对应的f=0，方案也不唯一,例如d(j,0) > d(j,1)且f(j,0)=0，
则f(i,0)=0

对于叶子节点i

1
2
d[i][0] = 0, f[i][0] = true
d[i][1] = 1, f[i][1] = true

看到没有? 我们需要考虑的dp状态 d[i][0]、d[i][1]、f[i][0]、f[i][1] 都仅仅和它的子节点有关. 而不需要考虑到它的孙子节点. 所以代码写起来会非常优雅和轻松. 因为仅仅和子节点有关是非常适合递归的.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//#include "stdafx.h"
#include <string>
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
//#define LOCAL
const int maxn = 205;
int n, top;
map<string, int> mina;
string name1, name2;
vector<int> g[maxn];
typedef vector<int>::iterator vit;
int d[maxn][2];
bool f[maxn][2];

void dfs(int cur, int fa)
{
	d[cur][0] = 0, f[cur][0] = true;
	d[cur][1] = 1, f[cur][1] = true;
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (*x==fa)
		{
			continue;
		}
		dfs(*x, cur);
		d[cur][1] += d[*x][0];
		f[cur][1] = f[cur][1] && f[*x][0];
		d[cur][0] += max(d[*x][0], d[*x][1]);
		if (d[*x][0]==d[*x][1])
		{
			f[cur][0] = false;
		}
		else if (d[*x][0]>d[*x][1])
		{
			f[cur][0] = f[cur][0] && f[*x][0];
		}
		else
		{
			f[cur][0] = f[cur][0] && f[*x][1];
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	while(cin>>n, n)
	{
		for (int i = 1;i<=n;i++)
		{
			g[i].clear();
		}
		mina.clear(); // 忘了clear, T到死啊~
		memset(d,0,sizeof(d));
		memset(f,0,sizeof(f));
		top = 0;
		cin>>name1;
		mina[name1] = ++top; // 大boss, 即根节点恒为1
		int nn = n;
		while(--nn)
		{
			cin>>name1>>name2;
			if (!mina.count(name1))
			{
				mina[name1] = ++top;
			}
			if (!mina[name2])
			{
				mina[name2] = ++top;
			}
			g[mina[name1]].push_back(mina[name2]);
			g[mina[name2]].push_back(mina[name1]);
		}
		dfs(1,0);
		bool ans;
		if (d[1][0]==d[1][1])
		{
			ans = false; // 既可以选根节点也可以不选根节点,那肯定不唯一
		}
		else if(d[1][0]>d[1][1])
		{
			ans = f[1][0];
		}
		else
		{
			ans = f[1][1];
		}
		printf("%d %s\n",max(d[1][0], d[1][1]), ans?"Yes":"No");
	}
	return 0;
}

ac情况

Status Accepted
Length 1693
Lang C++11 5.3.0
Submitted 2019-11-06 22:29:08
Shared
RemoteRunId 24157941

所以有的时候, 适当扩展dp对象的话, 可以化繁为简~

参考

【1】https://yfsyfs.github.io/2019/11/01/HDU-1693-Eat-the-Trees-%E6%8F%92%E5%A4%B4DP%E5%85%A5%E9%97%A8/