并查集练习---poj 1417 并查集+DP

这到题倒是和team them up 有些类似。

很容易得到：回答yes ，则x和y是相同集合的，反之，则是不同集合的。

首先用friend-enemy 并查集，注意：不要将朋友和敌人分开维护，这样容易出错。

得到了若干集合，每个集合有两个数，a和b。

现在要求n个集合中各挑出一个数(a或者b)，使得他们之和等于p1(说真话的人数)。而这个用dp可以很好的解决，用f[i][j]表示到第i个集合和为j个的情况数，我们还用过pre[i][j]记录当前选的是a还是b，用于后面判断状态。方程为f[i][j] = f[i1][ja] + f[i1][jb],j>=a,j>=b。如果最后f[n][p1] == 1说明是唯一的情况，输出该情况，否则输出 “no”(多解算no)注意点 : 按上面的dp写法，f[i][j]可能会很大，因为n可以达到三位数。其实我们关心的只是f[i][j] 等于0，等于1，大于1三种情况，所以当f[i][j] > 1时，我们都让它等于2即可

【代码】

#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=602;int p[N][N],f[N][N],d[N][2],fa[N],r[N],b[N];bool ans[N][2];int tot,n,p1,p2;int find(int x){    if (fa[x]==x) return x;    int t=fa[x];    fa[x]=find(fa[x]);    r[x]^=r[t];    return fa[x];}int main(){    int m,x,y,fx,fy,i,j;    char s[5];    freopen("in","r",stdin);    while (1)    {        scanf("%d%d%d",&m,&p1,&p2);        if (m==0 && p1==0 && p2==0) return 0;        n=p1+p2;        tot=0;        memset(f,0,sizeof(f));        memset(d,0,sizeof(d));        memset(ans,0,sizeof(ans));        memset(r,0,sizeof(r));        memset(p,0,sizeof(p));        memset(b,0,sizeof(b));        for (i=1;i<=n;i++)            fa[i]=i;        for (i=1;i<=m;i++)        {            scanf("%d%d %s",&x,&y,s);            fx=find(x);fy=find(y);            if (fx==fy) continue;            fa[fy]=fx;            if (s[0]=='y') r[fy]=r[x]^r[y]^0;            else r[fy]=r[x]^r[y]^1;        }        for (i=1;i<=n;i++)            if (find(i)==i)                b[i]=++tot;        for (i=1;i<=n;i++)            d[b[find(i)]][r[i]]++;        f[0][0]=1;        for (i=1;i<=tot;i++)            for (j=0;j<=n;j++)            {                if (j-d[i][0]>=0 && f[i-1][j-d[i][0]]>0)                {                    f[i][j]+=f[i-1][j-d[i][0]];                    p[i][j]=d[i][0];                }                if (j-d[i][1]>=0 && f[i-1][j-d[i][1]]>0)                {                    f[i][j]+=f[i-1][j-d[i][1]];                    p[i][j]=d[i][1];                }                if (f[i][j]>1) f[i][j]=2;            }        if (f[tot][p1]!=1)        {            printf("no\n");            continue;        }        for (i=tot,j=p1;i>0 && j>0;i--)        {            if (d[i][0]==p[i][j]) ans[i][0]=true;            else ans[i][1]=true;            j-=p[i][j];        }        for (i=1;i<=n;i++)            if (ans[b[find(i)]][r[i]])                printf("%d\n",i);        printf("end\n");    }}