poj1417.cpp

北大OJ 1417题的标程代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define maxn 310

int fat[maxn*2], prp[maxn*2], rec[maxn*2][2][maxn*2], cot[maxn*2][2], m, c[maxn*2][2], rf[maxn*2];
int s[maxn*2][maxn], chs[maxn*2][maxn], ans[maxn];

int getfather(int x)
{
	int fx;
	if(fat[x]!=x){
		fx=fat[x];
		fat[x]=getfather(fx);
		prp[x]*=prp[fx];
	}
	return fat[x];
}

void merge(int x, int y, int tmp)
{
	int fx, fy;
	fx=getfather(x); fy=getfather(y);
	fat[fy]=fx;
	prp[fy]=prp[x]*prp[y]*tmp;
}

void dp()
{
	int k, i, t;
	for(k=0; k<m; k++) memset(s[k], 0, sizeof(s[k]));
	s[0][c[0][0]]++; chs[0][c[0][0]]=0;
	s[0][c[0][1]]++; chs[0][c[0][1]]=1;
	for(k=1; k<m; k++){
		for(i=0; i<maxn; i++){
			t=i-c[k][0];
			if(t>=0 && s[k-1][t]>0) s[k][i]+=s[k-1][t], chs[k][i]=0;
			t=i-c[k][1];
			if(t>=0 && s[k-1][t]>0) s[k][i]+=s[k-1][t], chs[k][i]=1;
		}
	}
}

int main()
{
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	
	int q, p1, p2, n, i, k, x, fx, y, tmp, tot;
	bool fg;
	char str[5];
	
	while(scanf("%d %d %d", &q, &p1, &p2), q || p1 || p2){
		n=p1+p2;
		fg=1;
		if(p1==p2) fg=0;
		for(i=1; i<=n; i++) fat[i]=i, prp[i]=1;
		memset(cot, 0, sizeof(cot));
		
		while(q--){
			scanf("%d %d %s", &x, &y, str);
			if(str[0]=='y') tmp=1;
			else tmp=-1;
			merge(x, y, tmp);
		}
		
		for(x=1; x<=n && fg; x++){
			fx=getfather(x);
			if(prp[x]>0) rec[fx][0][cot[fx][0]++]=x;
			else rec[fx][1][cot[fx][1]++]=x;
		}
		
		m=0;
		for(i=1; i<=n && fg; i++)
			if(cot[i][0]+cot[i][1]){
				c[m][0]=cot[i][0]; c[m][1]=cot[i][1];
				rf[m++]=i;
				if(cot[i][0]==cot[i][1]) fg=0;
			}
		
//		printf("m=%d\n", m);
//		for(i=0; i<m; i++) printf("%d %d\n", c[i][0], c[i][1]);
		
		if(fg) dp();
		
		if(s[m-1][p1]!=1) fg=0;
		
		if(fg){
			tot=0;
			for(k=m-1; k>=0; k--){
				fx=rf[k];
				if(chs[k][p1]==0){
					for(i=0; i<cot[fx][0]; i++) ans[tot++]=rec[fx][0][i];
					p1-=c[k][0];
				}
				else{
					for(i=0; i<cot[fx][1]; i++) ans[tot++]=rec[fx][1][i];
					p1-=c[k][1];
				}
			}
			sort(ans, ans+tot);
			for(i=0; i<tot; i++) printf("%d\n", ans[i]);
			printf("end\n");
		}
		else printf("no\n");
	}
	
	return 0;
}