poj3342 Party at Hali-Bula

[cpp]
/*
用dp[i][1]表示选择结点i时以i为跟结点的子树能得到的最大值，dp[i][0]为不选i时的最大值，
则dp[i][0]+=max(dp[j][0],dp[j][1]),dp[i][1]+=sum{dp[j][0]},其中j为i的儿子；
边界为d[k][1]=1,d[k][0]=0(k为叶子节点)
本题比较难一点的是判断解得唯一性。我的判断方法是：如果dp[i][0]>=dp[i][1],
且dp[j][0]==dp[j][1](j为i的孩子），就可以判定为不唯一了。
对于根结点如果dp[0][1]==dp[0][0] 可知不唯一；
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define MAXSIZE 1000
#define sf scanf
#define pf printf
#define __int64 long long
#define INF 0xfffffff
using namespace std;
struct node
{
    int v,next;
}edge[MAXSIZE*4];
int head[MAXSIZE],ant,dp[MAXSIZE][2];
char s[250][20];
void add(int u,int v)
{
    edge[ant].v=v;
    edge[ant].next=head[u];
    head[u]=ant++;
}
void DFS(int r,int f)
{
    dp[r][1]=1;
    dp[r][0]=0;
    for(int i=head[r];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f) continue;
        DFS(v,r);
        dp[r][0]+=max(dp[v][0],dp[v][1]);
        dp[r][1]+=dp[v][0];
    }
}
bool cheak(int n)
{
    for(int i=0;i<n;i++)
    {
        if(dp[i][0]>=dp[i][1])
        {
            for(int j=head[i];j!=-1;j=edge[j].next)
            {
                int v=edge[j].v;
                if(i==v) continue;
                if(dp[v][0]==dp[v][1]) return false;
            }
        }
    }
    return true;
}
int main()
{
    int n,sum;
    while(sf("%d",&n),n)
    {
        ant=0;
        sum=1;
        memset(dp,0,sizeof(dp));
        memset(head,-1,sizeof(head));
        char a[20],b[20];
        scanf("%s",s[0]);
        int u,v;
        for(int i=1;i<n;i++)
        {
            u=v=-1;
            scanf("%s%s",&a,&b);
            for(int i=0;i<sum;i++)
            {
                if(strcmp(a,s[i])==0) {u=i;}
                if(strcmp(b,s[i])==0) {v=i;}
            }
            if(u==-1) {u=sum;strcpy(s[sum++],a);}
            if(v==-1) {v=sum;strcpy(s[sum++],b);}
            //cout<<u<<" "<<v<<endl;
            add(u,v);
            add(v,u);
        }
        DFS(0,-1);

        int worth=max(dp[0][0],dp[0][1]);
        bool flag=cheak(sum);
        if(dp[0][0]==dp[0][1]) flag=false;
        cout<<worth<<" ";
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

补充：软件开发 , C++ ,