题目分析：
树形dp+判断
状态转移方程:
对于叶子节点 dp[k][0] = 0, dp[k][1] = 1
对于非叶子节点i,
dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i的儿子)
dp[i][1] = 1 + ∑dp[j][0] (j是i的儿子)
最多人数即为max(dp[0][0], dp[0][1])
如何判断最优解是否唯一
有点难啊！！！！
新加一个状态dup[i][j]，表示相应的dp[i][j]是否是唯一方案。
对于叶子结点, dup[k][0] = dup[k][1] = 1.
对于非叶子结点,
对于i的任一儿子j，若(dp[j][0] > dp[j][1] 且 dup[j][0] == 0) 或 (dp[j][0] < dp[j][1] 且 dup[j][1] == 0) 或 (dp[j][0] == dp[j][1])，则dup[i][0] = 0
对于i的任一儿子j有dup[j][0] = 0, 则dup[i][1] = 0
这是http://blog.sina.com.cn/s/blog_89e848330100x07r.html的代码，感觉写的比较好！！！自己还没弄懂
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char name[220][110],str1[110],str2[110];
int dp[220][2],dup[220][2];
int k;
struct node
{
int next[220];
int num;
}p[220];
int search(char c[])
{
int i;
for( i=1;i<=k;i++)
{
if(strcmp(name[i],c)==0)return i;
}
k++;
strcpy(name[k],c);
return k;
}
int max(int x,int y)
{
if(x>y)return x;
else return y;
}
void dfs(int root)
{
int j,u;
dp[root][0]=0;
dp[root][1]=1;
dup[root][0]=1;
dup[root][1]=1;
for(j=0;j<p[root].num;j++)
{
u=p[root].next[j];
dfs(u);
dp[root][0]+=max(dp[u][0],dp[u][1]);
dp[root][1]+=dp[u][0];
if(dp[u][0]>dp[u][1] && dup[u][0]==0) dup[root][0]=0;
else if(dp[u][1]>dp[u][0] && dup[u][1]==0) dup[root][0]=0;
else if(dp[u][0]==dp[u][1]) dup[root][0]=0;
if(dup[u][0]==0) dup[root][1]=0;
}
}
int main()
{
int i,j,n;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=0;i<220;i++)p[i].num=0;
scanf("%s",name[1]);
k=1;
int ans1,ans2;
for(i=1;i<n;i++)
{
scanf("%s%s",str1,str2);
int ans1=search(str1);
int ans2=search(str2);
p[ans2].next[p[ans2].num]=ans1;
p[ans2].num++;
}
memset(dp,0,sizeof(dp));
dfs(1);
if(dp[1][0]>dp[1][1] && dup[1][0]==1) printf("%d Yes\n",dp[1][0]);
else if(dp[1][1]>dp[1][0] && dup[1][1]==1) printf("%d Yes\n",dp[1][1]);
else printf("%d No\n",max(dp[1][0],dp[1][1]));
}
}
参照别人的ppt写的代码一直有错误 还没找到，我自己的代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[1000][10],vis[1000];
//dp[i][0]代表不选i,i及其子树所能选出的最多人数；
//dp[i][1]代表选i，i及其子树所能选出的最多人数；
int dup[1000][10];//代表dp[i][j]的方案数是否唯一
int a[200];//a[i]代表i的boss是a[i]
int n;
char maze1[300][110],maze2[300][110];
int dfs(int x,int y)//记忆化搜索
{
int ans=0;
if(dp[x][y]!=-1)
return dp[x][y];
if(y==0)
{
for(int i=1;i<=n;i++)//求x的叶子节点
if(a[i]==x&&a[i]!=i)//排除i是叶子节点
ans+=max(dfs(i,0),dfs(i,1));
dp[x][y]=ans;
}
if(y==1)
{
for(int i=1;i<=n;i++)
if(a[i]==x&&a[i]!=i)//排除i是叶子节点
ans+=dfs(i,0);
dp[x][y]=ans+1;
}
return dp[x][y];
}
int dfs_dup(int x,int y)
{
int ans;
if(dup[x][y]!=-1)
return dup[x][y];
int flag=0,temp1,temp2;
for(int i=1;i<=n;i++)
if(a[i]==x&&a[i]!=i)//寻找子节点
{
temp1=dfs(i,0);
temp2=dfs(i,1);
if((temp1>temp2&&dfs_dup(i,0)==0)||(temp1<temp2&&dfs_dup(i,1)==0)||temp1==temp2)
{
dup[x][0]=0;
flag=1;
break;
}
if(dfs_dup(i,0)==0)
dup[x][1]=0;
}
/*if(flag==0)
dup[x][1]=1;*/
if(y==0)
return dup[x][0];
else
return dup[x][1];
//return dup[x][y];
}
int main()
{
char s[1000];
while(scanf("%d",&n)!=EOF && n!=0)
{
getchar();
//初始化
memset(dp,-1,sizeof(dp));
memset(vis,0,sizeof(vis));
memset(dup,-1,sizeof(dup));
for(int i=1;i<=n;i++)
a[i]=i;
for(int i=1;i<=n;i++)
{
gets(s);
sscanf(s,"%s %s",maze1[i],maze2[i]);
}
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)//j代表boss
if(strcmp(maze2[i],maze1[j])==0)
a[i]=j;
for(int i=1;i<=n;i++)
vis[a[i]]=1;//不是叶子节点标记为1，
for(int i=1;i<=n;i++)
if(vis[i]==0)//叶子节点
{
dp[i][0]=0;
dp[i][1]=1;
dup[i][0]=1;
dup[i][1]=1;
}
/* for(int i=1;i<=n;i++)
if(vis[i]==0)
{
printf("i= %d %d %d***\n",i,dup[i][0],dup[i][1]);
}*/
int ans=max(dfs(1,0),dfs(1,1));
int flag=0;
int temp1=dfs(1,0);
dfs_dup(1,0);
dfs_dup(1,1);
if(ans==temp1)
flag=dfs_dup(1,0);
else
flag=dfs_dup(1,1);
for(int i=1;i<=n;i++)
printf("%d %d***\n",dup[i][0],dup[i][1]);
//*********方案数是否唯一
/* for(int i=1;i<=n;i++)//检查建树是否正确
printf("%d %d***\n",i,a[i]);*/
/*for(int i=1;i<=n;i++)
printf("%d %d****\n",dp[i][0],dp[i][1]);*/
if(flag==1)
printf("%d Yes\n",ans);
else
printf("%d No\n",ans);
}
system("pause");
return 0;
}