poj3342实在不知道错哪了。

C/C++ code

#include<iostream>#include<cstdio>#include<string>#include<string.h>#include<algorithm>using namespace std;int dp[201][2];//以i号节点为根的树所能选的最大节点数:dp[i][]// 不选i号节点：dp[i][0]=sum(max(dp[son[i][j]][1],dp[son[i][j]][0]));选i号节点：dp[i][1]=sum(dp[son[i][j]][0])+1;//  初始化：dp[叶子][0]=0;  dp[叶子][1]=1; 由叶向根树形dpint son[201][201],deep[201];void bfs(int node,int T,int d){    deep[node]=d;    for(int i=0;i<T;i++)    {        if(son[node][i]==1)        bfs(i,T,d+1);    }}int main(){    int i,j,k;    int T,tmp1,tmp2;    while(scanf("%d",&T)&&T)    {        j=1;        string str[201];        memset(son,0,sizeof(son));  memset(deep,0,sizeof(deep));        cin>>str[0];        string s1,s2;        for(i=0;i<T-1;i++)        {            tmp1=tmp2=-1;            int flag=0;            cin>>s1>>s2;            for(k=0;k<j;k++)//对于输入的字符串进行处理            {                if(s1==str[k])                { tmp1=k; flag=2; if(tmp2!=-1)  {flag=0; break;} continue; }                if(s2==str[k])                { tmp2=k; flag=1; if(tmp1!=-1)  {flag=0; break;} continue; }            }            if(k==j&&flag==1)//s2找到了匹配串，s1没有找到            { str[j++]=s1; son[tmp2][j-1]=1;}            else if(k==j&&flag==2)//s1找到了匹配串  ，s2没有找到            { str[j++]=s2; son[j-1][tmp1]=1;}            else if(k!=j&&flag==0)//s1 s2都找到了匹配串            { son[tmp2][tmp1]=1;  }            else if(k==j&&flag==0)//s1  s2都未找到匹配串            {                tmp1=j;  str[j++]=s1;                tmp2=j;  str[j++]=s2;                son[tmp2][tmp1]=1;            }        }        bfs(0,T,0);//计算每个节点所在树的深度,boss节点为0层        int MAX=-1;        for(i=0;i<T;i++)        { MAX=max(MAX,deep[i]); }//MAX记录最大深度,即叶子        for(i=0;i<T;i++)//在son中转存儿子的形式,son[i][0] i号节点有几个儿子        {            son[i][0]=0;            for(j=1,k=1;j<T;j++)            if(son[i][j]==1)            {                son[i][0]++;  son[i][k++]=j;            }        }        memset(dp,0,sizeof(dp));        for(i=0;i<T;i++)//初始化        {            if(deep[i]==MAX)            dp[i][1]=1;        }        for(i=MAX-1;i>=0;i--)//由叶向根dp        {            for(j=0;j<T;j++)            {                if(deep[j]==i)                {                    for(k=1;k<=son[j][0];k++)                    {  dp[j][0]+=(max(dp[son[j][k]][1],dp[son[j][k]][0]));    dp[j][1]+=dp[son[j][k]][0];  }                    dp[j][1]++;                }            }        }        if(dp[0][1]==dp[0][0])  { printf("%d No\n",dp[0][0]); continue;}        MAX=max(dp[0][0],dp[0][1]);//检验是否唯一        for(i=1;i<T;i++)        {            if(MAX==dp[i][1]||MAX==dp[i][0])            break;        }        if(i==T)        printf("%d Yes\n",MAX);        else        printf("%d No\n",MAX);    }    return 0;}