学海泛舟

UVa 1220 Party at Hali-Bula 题解

发表于 | 分类于 |

原题

传送门

题目大意

n个人组成的树型结构，要求选最多的人参加晚会，但不能同时选一个人和他的直属上司，求最多的人数和在人数最多的前提下，方案是否唯一

分析

这道就是一个树的最大独立集问题，但要求判断方案是否唯一。
如果我们用d(u,0)和d(u,1)分别表示以u为根的子树中，不选u所能得到的最大人数和选u所能得到的最大人数，那么同样我们可以在设一个f(u,0)和f(u,1)表示在方案的唯一性(f(…)=1表示唯一，f(…)=0表示不唯一)。
然后我们考虑转移方程。
对于d(u,1)，由于u已经选择了，那么u的所有子节点都不能选，所以d(u,1)=sum(d(v,0))+1,而且容易知道，只有每个f(v,0)=1,f(u,1)才是1.
对于d(u,0)，由于u没有选，对于u的所有子节点都可以选或者不选，所以d(u,0)=sum(max(d(v,0),d(v,1)))，这里的唯一性要考虑两个方面，其一，如果d(v,0)=d(v,1)，那么结果是不唯一的，其二，如果max取得的那个结果所对应的f=0，那么结果显然也是不唯一的

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int maxn=200+5;
map<string,int> mp;
vector<int> vc[maxn];
int d[maxn][2];
int f[maxn][2];
void dp(int root){
    d[root][1]=1;
	for(int i=0;i<vc[root].size();++i){
		int v=vc[root][i];
		if(f[v][0]==-1) dp(v);
		d[root][1]+=d[v][0];
		if(f[v][0]==0) f[root][1]=0;
	}
	if(f[root][1]==-1) f[root][1]=1;
	for(int i=0;i<vc[root].size();++i){
		int v=vc[root][i];
		d[root][0]+=max(d[v][1],d[v][0]);
		if(d[v][1]==d[v][0]) f[root][0]=0;
		if(d[v][1]>d[v][0]&&f[v][1]==0) f[root][0]=0;
		if(d[v][1]<d[v][0]&&f[v][0]==0) f[root][0]=0;
	}
	if(f[root][0]==-1) f[root][0]=1;
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF&&n){
		mp.clear();
		for(int i=0;i<maxn;++i){
			vc[i].clear();
		}
		memset(d,0,sizeof d);
		memset(f,-1,sizeof f);
		string a,b;
		cin>>a;
		int cnt=1;
		if(mp[a]==0) mp[a]=cnt++;
		for(int i=1;i<n;++i){
			cin>>a>>b;
			if(mp[a]==0) mp[a]=cnt++;
			if(mp[b]==0) mp[b]=cnt++;
			vc[mp[b]].push_back(mp[a]);
		}
		dp(1);
		if(d[1][0]==d[1][1]){
			printf("%d No\n",d[1][0]);
		} else if (d[1][0]>d[1][1]) {
			printf("%d ",d[1][0]);
			if(f[1][0]==1) printf("Yes\n");
			else printf("No\n");
		} else {
			printf("%d ",d[1][1]);
			if(f[1][1]==1) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}