《算法竞赛进阶指南》数据结构进阶练习题
我的思路是并查集加分组背包,不同种的两个人不能同时选。改了一晚上一直有几个点过不去,请大佬们帮忙看看,谢谢!
#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;
}