這到題倒是和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
