POJ1417(True Liars)

链接：https://vjudge.net/problem/POJ-1417
思路：首先我们先明白，当a指认b时，ab就已经有关系并且不可分离了，所以自然而然就是并查集，并且为种类并查集，同时满足模2加法运算，即a说b坏人，b说c坏人，那么a和c一定是同类人，我们就这样维护一个种类并查集，完成之后可能有多个块，每个块都可以有两种取值方式，这时候就变成一个01背包问题的变形了，做一次背包然后逆推找到路径即可。(注意并查集完成时并没有全部进行路径压缩，所以要手动压缩一遍！！！切记切记就是在这里错了一天！！！)
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

int n,p,q,nn;
const int maxn = 1010;
int par[maxn];
int rel[maxn];
int num[maxn];
int w[maxn][2];
int dp[maxn][maxn];
int cho[maxn];
int bcc[maxn];

int getroot(int a){
    if(a==par[a])return a;
    int px = par[a];
    par[a] = getroot(par[a]);
    rel[a] = (rel[a]+rel[px]+2)%2;
    return par[a];
}

void merge(int a,int b,int r){
    int p1 = getroot(a);
    int p2 = getroot(b);
    if(p1==p2)return;
    par[p2] = p1;
    num[p1]+=num[p2];
    num[p2] = 0;
    rel[p2] = (rel[a]+r-rel[b]+2)%2;//根据矢量图得到的转移式子
}

int main(){
    while(~scanf("%d%d%d",&nn,&p,&q)&&(nn||p||q)){
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        memset(bcc,0,sizeof(bcc));
        memset(cho,0,sizeof(cho));
        n = p+q;
        for(int i=1;i<=n;i++){
            par[i] = i;
            num[i] = 1;
            rel[i] = 0;
        }
        for(int i=0;i<nn;i++){
            int a,b;
            char ch[10];
            scanf("%d%d%s",&a,&b,ch);
            int r;
            if(ch[0]=='y')r = 0;
            else r = 1;
            merge(a,b,r);
        }
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(num[i]){
                bcc[i] = ++cnt;//扫描集合的个数
            }
        }
        for(int i=1;i<=n;i++){
            getroot(i);//切记切记一定要手动把所有路径都压缩这样才能完成后面的记数
            w[bcc[par[i]]][rel[i]]++;
        }
        dp[0][0] = 1;
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<=p;j++){
                if(j>=w[i][0])dp[i][j] = dp[i-1][j-w[i][0]];
                if(j>=w[i][1])dp[i][j] += dp[i-1][j-w[i][1]];
            } 
        }
        if(dp[cnt][p]==1){//学习别人简单的寻找路径方法，自己不知道写了些什么乱七八糟的东西
            int j = p;
            for(int i=cnt; i>=1; i--){
                if(dp[i][j]==dp[i-1][j-w[i][0]]){
                    cho[i] = 0;
                    j-=w[i][0];
                }
                else if(dp[i][j]==dp[i-1][j-w[i][1]]){
                    cho[i] = 1;
                    j-=w[i][1];
            }
            }
        for(int i=1;i<=n;i++){
            int ff = bcc[par[i]];
            if(cho[ff]==rel[i])
              printf("%d\n",i);
        }
        printf("end\n");
    }
        else printf("no\n");
    }
    return 0;
}