这题第一步肯定就是并查集啦。
对于一个块分成两个集合，相同和不同
然后进行背包二选一
但是有两种情况得开二维
然而出答案的时候也不能省，因为有可能没选好就到答案。。
主要是麻烦。。。很麻烦。。。
#include#include #include #include #include #include using namespace std;int fa[610],da[610];int findfa(int x){ if(fa[x]<0)return x; int f=findfa(fa[x]); da[x]^=da[fa[x]], fa[x]=f; return fa[x];}int len,c[2][610],id[610],v[2][610];int f[610][610],d[2][610][610],aslen,as[610];char ss[10];int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); int n,x,y,p1,p2; while(scanf("%d%d%d",&n,&p1,&p2)!=EOF) { if(n==0&&p1==0&&p2==0)break; for(int i=1;i<=p1+p2;i++)fa[i]=-1,da[i]=0; for(int i=1;i<=n;i++) { scanf("%d%d%s",&x,&y,ss+1); int fx=findfa(x),fy=findfa(y); if(fx!=fy) fa[fy]+=fa[fx], fa[fx]=fy, da[fx]=da[x]^da[y]^(ss[1]=='n'); } //----------计算关系---------------- memset(v,0,sizeof(v)); for(int i=1;i<=p1+p2;i++) { int fi=findfa(i); v[da[i]][fi]++; } len=0; for(int i=1;i<=p1+p2;i++) if(findfa(i)==i) { len++; c[0][len]=v[0][i]; c[1][len]=v[1][i]; id[len]=i; } //----------init--------------------- memset(f,0,sizeof(f));f[0][0]=1; for(int i=1;i<=len;i++) { for(int j=p1;j>=0;j--) { if(j-c[0][i]>=0&&f[i-1][j-c[0][i]]>0) { f[i][j]+=f[i-1][j-c[0][i]]; } if(j-c[1][i]>=0&&f[i-1][j-c[1][i]]>0) { f[i][j]+=f[i-1][j-c[1][i]]; } } } //-----------check----------------- if(f[len][p1]!=1)printf("no\n"); else { int now=0; memset(d,0,sizeof(d));d[0][0][0]=1; for(int i=1;i<=len;i++) { now^=1; memset(d[now],0,sizeof(d[now])); for(int j=p1;j>=0;j--) { if(j-c[0][i]>=0&&d[now^1][j-c[0][i]][0]>0) { for(int k=0;k<=d[now^1][j-c[0][i]][0];k++)d[now][j][k]=d[now^1][j-c[0][i]][k]; d[now][j][++d[now][j][0]]=id[i]; } if(j-c[1][i]>=0&&d[now^1][j-c[1][i]][0]>0) { for(int k=0;k<=d[now^1][j-c[1][i]][0];k++)d[now][j][k]=d[now^1][j-c[1][i]][k]; d[now][j][++d[now][j][0]]=-id[i]; } } } //------------findans-------------- aslen=0; for(int i=2;i<=d[now][p1][0];i++) { int p=0; if(d[now][p1][i]<0)p^=1,d[now][p1][i]=-d[now][p1][i]; for(int j=1;j<=p1+p2;j++) if(findfa(j)==d[now][p1][i]&&(da[j]^p)==0)as[++aslen]=j; } sort(as+1,as+aslen+1); for(int i=1;i<=aslen;i++)printf("%d\n",as[i]); printf("end\n"); } //----------print ans------------------ } return 0;}