并查集练习---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[i–1][j–a] + f[i–1][j–b],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即可
【代码】

[cpp] view plaincopyprint?
#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");
    }
}

作者：ascii991

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