这道题使用了
并查集+背包
这里我们使用一般的并查集
f[i]表示i是天使时的集合的代表元素
f[i+p1+p2]表示i是恶魔时的集合的代表元素
当一个人回答另一个人是否是天神时
回答yes代表两人身份相同
天神说另一个天神是天神
恶魔说另一个恶魔是天神
回答no代表两人身份不同
天神说恶魔是恶魔
恶魔说天神是恶魔
每一次处理关系:
同类就合并(x,y),(x+p1+p2,y+p1+p2)
异类就合并(x+p1+p2,y),(x,y+p1+p2)
统计每一个集合里的两个阵营的人数
用 两个阵营的人数差 作为 体积
dp[i]表示i这个差值能否被达到
tot[i]便是达到i这个差值的方案数
当方案数>1时,tot[i]为2
pos[i]记录i这个状态是由哪个i-k转移的来的
倒推回去,得到每个集合的正确贡献
把天使记录一下,按升序输出
下面是AC代码
#include<bits/stdc++.h>
using namespace std;
int n,p1,p2;
int f[600*2+5];
void chu()
{
for(int i=1;i<=(p1+p2)*2;i++)
{
f[i]=i;
}
}
int find(int l)
{
if(f[l]!=l)
f[l]=find(f[l]);
return f[l];
}
void tl(int x,int y)
{
int fx=find(x);
int fy=find(y);
f[fy]=fx;
}
struct qw{
int val;
int ci;
}size[1605];
int b[1605];
int c[1605];
int t=0;
int now=0;
int dp[605*2];
int pos[1605];
int tot[1605];
int used[1605];
int vis[1605];
bool an[1205];
void p(int x,int iff)
{
if(iff==1)
{
if(b[x]<c[x])
{
for(int i=1;i<=p1+p2;i++)
{
if(find(i)==x)
{
an[i]=1;
}
}
}
else
{
for(int i=p1+p2+1;i<=(p1+p2)*2;i++)
{
if(find(i)==x)
{
an[i-p1-p2]=1;
}
}
}
}
else
{
if(b[x]>c[x])
{
for(int i=1;i<=p1+p2;i++)
{
if(find(i)==x)
an[i]=1;
}
}
else
{
for(int i=p1+p2+1;i<=(p1+p2)*2;i++)
{
if(find(i)==x)
an[i-p1-p2]=1;
}
}
}
}
int main()
{
while(1)
{
cin>>n>>p1>>p2;
if(n==0&&p1==0&&p2==0)
return 0;
chu();
int xx,yy;
string s;
for(int ll=1;ll<=n;ll++)
{
scanf("%d %d",&xx,&yy);
cin>>s;
if(xx==yy)
continue;
if(s[0]=='y')
{
if(find(xx)!=find(yy))
{
tl(xx,yy);
tl(xx+p1+p2,yy+p1+p2);
}
}
else
{
if(find(xx+p1+p2)!=find(yy))
{
tl(xx+p1+p2,yy);
tl(xx,yy+p1+p2);
}
}
}
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=1;i<=(p1+p2)*2;i++)
{
int fb=find(i);
if(i<=p1+p2&&fb>p1+p2)
{
fb-=p1+p2;
c[fb]++;
}
else
{
if(i<=p1+p2)
b[fb]++;
}
}
t=0;
now=0;
for(int i=1;i<=p1+p2;i++)
{
if(b[i]!=0||c[i]!=0)
{
// cout<<b[i]<<" "<<c[i]<<" ";
size[++t].val=abs(b[i]-c[i]);
size[t].ci=i;
now+=max(b[i],c[i]);
}
}
memset(dp,0,sizeof(dp));
memset(tot,0,sizeof(tot));
memset(pos,0,sizeof(pos));
memset(used,0,sizeof(used));
dp[0]=1;
tot[0]=1;
int k=now-p1;
// cout<<k;
for(int i=1;i<=t;i++)
{//cout<<size[i].val<<" ";
for(int j=k;j>=size[i].val;j--)
{
//
if(dp[j-size[i].val]==1)
{
if(dp[j]==0)
{
dp[j]=1;
pos[j]=j-size[i].val;
tot[j]=tot[j-size[i].val];
used[j]=i;
}
else
tot[j]=2;
}
}
}
if(tot[k]>1)
{
cout<<"no"<<endl;
}
else
{
memset(vis,0,sizeof(vis));
while(k)
{
vis[used[k]]=1;
k=pos[k];
}
memset(an,0,sizeof(an));
for(int i=1;i<=t;i++)
{
if(vis[i])
{
p(size[i].ci,1);
}
else
p(size[i].ci,0);
}
for(int i=1;i<=p1+p2;i++)
if(an[i])
printf("%d\n",i);
printf("end\n");
}
}
return 0;
}