True Liars

《算法竞赛进阶指南》数据结构进阶练习题

我的思路是并查集加分组背包，不同种的两个人不能同时选。改了一晚上一直有几个点过不去，请大佬们帮忙看看，谢谢！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e3+10;
int m,n,p,q,cnt,a[N],ans[N],fa[N],siz[N],f[N],d[N];
char ch[4];
int Get(int x){
	if(x==fa[x])
		return x;
	return fa[x]=Get(fa[x]);
}
void Merge(int x,int y){
	x=Get(x),y=Get(y);
	if(x==y)
		return;
	fa[x]=y,siz[y]+=siz[x];
}
int main(){
	while(cin>>m>>p>>q){
		if(m==0&&p==0&&q==0)
			break;
		n=p+q,cnt=0;
		for(int i=1;i<=2*n;i++)
			fa[i]=i,siz[i]=0;
		for(int i=1;i<=n;i++)
			siz[i]=1;
		int x,y;
		for(int i=1;i<=m;i++){
			cin>>x>>y>>ch;
			if(ch[0]=='y')
				Merge(x,y),Merge(x+n,y+n);
			else
				Merge(x,y+n),Merge(x+n,y);
		}
		if(p==0){
			cout<<"end"<<endl;
			continue;
		}
		if(q==0){
			for(int i=1;i<=p;i++)
				cout<<i<<endl;
			cout<<"end"<<endl;
			continue;
		}
		for(int i=1;i<=n;i++)
			if(Get(i)==i)
				a[++cnt]=i;
		memset(f,0,sizeof(f));
		f[0]=1;
		for(int i=1;i<=cnt;i++){
			x=a[i];
			for(int j=p;j>=0;j--){
				for(int k=x;k<=2*n;k+=n){
					y=Get(k);
					if(siz[y]<=j&&siz[y]!=0){
						f[j]+=f[j-siz[y]];
						if(f[j]==f[j-siz[y]])
							d[j]=y;
					}
				}
			}
		}
		if(f[p]==0||f[p]>1)
			cout<<"no"<<endl;
		else{
			int len=0;
			while(p>0){
				for(int i=1;i<=n;i++)
					if(Get(i)==d[p])
						ans[++len]=i;
				p-=siz[d[p]];
			}
			sort(ans,ans+len+1);
			for(int i=1;i<=len;i++)
				cout<<ans[i]<<endl;
			cout<<"end"<<endl;
		}
	}
	return 0;
}