首页 > 代码库 > 【poj3342】 Party at Hali-Bula

【poj3342】 Party at Hali-Bula

2024-08-15 12:47:58   215人阅读

http://poj.org/problem?id=3342 (题目链接)

题意

　　给出一棵树，要求在不存在两个节点相邻的条件下，选出尽可能多的节点，并且判断是否有多种选法。

Solution

　　很水的树形dp，2个月前的自己Wa的不要不要的，现在的自己1A。。

　　f[i][0]表示i不去的最大人数，f[i][1]表示i去的最大人数。关键是如何去判断方案的唯一性。

　　对于节点x，我们分情况讨论。

　　1.x去更优。f[x][1]只能由f[son[x]][0]转移过来，那么方案肯定是唯一的，所以我们直接去搜索son[x]的儿子节点。

　　2.x不去更优。f[x][0]能由f[son[x]][0]或者是f[xon[x]][1]转移过来，而如果f[x][0]的值可以由多种方案得到，那么必然是x的某个儿子节点去和不去的人数相等。

　　3.x去与不去的人数相等。那么直接返回1。。

　　至此，问题已经解决。

代码

// poj3342#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<string>#include<cmath>#include<map>#define MOD 100003#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;const int maxn=300;struct edge {int to,next;}e[maxn<<1];map<string,int> mp;int head[maxn],f[maxn][2],cnt,n,m;void link(int u,int v) {	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void Init() {	mp.clear();cnt=n=0;	memset(head,0,sizeof(head));	memset(f,0,sizeof(f));}void dfs(int x) {	f[x][0]=0;f[x][1]=1;	for (int i=head[x];i;i=e[i].next) {		dfs(e[i].to);		f[x][0]+=max(f[e[i].to][1],f[e[i].to][0]);		f[x][1]+=f[e[i].to][0];	}}bool check(int x) {	if (f[x][0]==f[x][1]) return 0;	if (f[x][0]>f[x][1]) {		for (int i=head[x];i;i=e[i].next)			if (!check(e[i].to)) return 0;	}	else {		for (int i=head[x];i;i=e[i].next)			for (int j=head[e[i].to];j;j=e[j].next)				if (!check(e[j].to)) return 0;	}	return 1;}int main() {	while (scanf("%d",&m)!=EOF && m) {		Init();		string s1,s2;		cin>>s1;mp[s1]=(n=1);		for (int i=1;i<m;i++) {			cin>>s1>>s2;			if (!mp[s1]) mp[s1]=++n;			if (!mp[s2]) mp[s2]=++n;			link(mp[s2],mp[s1]);		}		dfs(1);		printf("%d %s\n",max(f[1][0],f[1][1]),check(1) ? "Yes" : "No");	}	return 0;}

　　

【poj3342】 Party at Hali-Bula


联系
我们