题意：有这么一群人，一群好人，和一群坏人，好人永远会说实话，坏人永远说假话，现在给你一组对话和好人与坏人的数目P1， P2。

数据里面的no是A说B是坏人， yes代表A说B是好人，就是这样，问题能不能从这些话里面得出来唯一的解，就是可以确定谁是好人谁是坏人，如果不能输出no，如果可以输出所有的好人。

分析，可以把这些人依据他们中的关系分成几个小集合，集合里面保存两类人的数目，然后DP求出来好人或者坏人是不是唯一的即可，‘

注意并查集时候可以这么认为凡是yes都是同类，no都是异类

///

 #include<iostream>

#include<algorithm>

#include<stdio.h>

#include<math.h>

#include<

string.h>

#include<queue>

using 

namespace std;

const 

int maxn = 

605;

struct people

{

    

int father, relation;

    

int same, other;

//

同类数目，和异类数目

    

int True;

//

是说谎者还是诚实者

}p[maxn];

int dp[maxn][maxn];

int Find(

int x)

{

    

int k = p[x].father;

    

if( p[x].father != x )

    {

        p[x].father = Find(k);

        p[x].relation = (p[x].relation+p[k].relation)%

2;

    }

    

return p[x].father;

}

int main()

{

    

int M, T, L;

    

while(scanf(

"

%d%d%d

", &M, &T, &L), M+T+L)

    {

        

int i, j, u, v, ru, rv, ok=

0, d, N=T+L, k=

1;

        

char s[

10];

int f[maxn];

//

f记录最后小集体的头结点

        

for(i=

0; i<=N; i++)

        {

            p[i].father = i;

            p[i].other = 

0;

            p[i].same = 

1;

//

自己和自己是同类，所以最少也有一个

            p[i].relation = 

0;

            p[i].True = 

0;

        }

        

while(M--)

        {

            scanf(

"

%d%d%s

", &u, &v, s);

            

if(ok)

continue;

            ru = Find(u), rv = Find(v);

            

if(s[

0] == 

'

y

')

                d = 

0;

//

0表示同类，1表示异类

            

else d = 

1;

            

if(ru == rv && (p[v].relation+p[u].relation)%

2 != d)

                ok = 

1;

            

else 

if(ru != rv)

            {

                p[ru].father = rv;

                p[ru].relation = (p[u].relation+p[v].relation+d)%

2;

            }

        }

        

if(!ok)

//

有可能说的话有矛盾

        {

            

for(i=

1; i<=N; i++)

            {

                u = Find(i);

                

if(u == i)

                    f[k++] = i;

                

else

                {

                    p[u].other += p[i].relation;

                    p[u].same += 

1-p[i].relation;

                }

            }

            memset(dp, 

0, 

sizeof(dp));

            dp[

1][ p[ f[

1] ].same ] += 

1;

            dp[

1][ p[ f[

1] ].other ] += 

1;

            

for(i=

2; i<k; i++)

            {

                u = f[i];

                

for(j=

0; j<=N; j++)

                {

                    

if(dp[i-

1][j])

                    {

                        dp[i][ p[u].same+j ] += dp[i-

1][j];

                        dp[i][ p[u].other+j ] += dp[i-

1][j];

                    }

                }

            }

        }

        

if(dp[k-

1][L] != 

1 || ok)

            printf(

"

no\n

");

        

else

        {

            

for(i=k-

1; i>

0; i--)

            {

                u = f[i];

                v = p[u].same;

                

if( (i!=

1 && dp[i-

1][T-v] != 

0) || (i==

1 && T==v) )

                {

                    p[u].True = 

1;

                    T -= v;

                }

                

else

                    T -= p[u].other;

            }

            

for(i=

1; i<=N; i++)

            {

                u = p[i].father;

                

if(p[u].True && !p[i].relation || p[u].True==

0 && p[i].relation)

                    printf(

"

%d\n

", i);

            }

            printf(

"

end\n

");

        }

    }

    

return 

0;

}

/*

1 1 1

1 2 yes

*/