记录编号	593661	评测结果	A
题目名称	[POJ 1417]真正的说谎者	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2024-09-06 22:04:13	内存使用	7.49 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
const int maxn = 1005;
set<int>st;
int s[maxn];
int r[maxn];
int f[maxn];
int dp[maxn][maxn];
int a[maxn][2];
inline void clear_set()
{
	st.clear();
	for(int i = 0;i < maxn;i++){
		s[i] = i;
	}
	memset(r,0,sizeof(r));
	memset(f,0,sizeof(f));
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
}
int find_set(int x)
{
	if(x != s[x]){
		int f = s[x];
		s[x] = find_set(s[x]);
		r[x] = (r[x]+r[f])%2;
	}
	return s[x];
}
inline void union_set(int x,int y,int z)
{
	int fx = find_set(x);
	int fy = find_set(y);
	if(fx != fy){
		s[fy] = fx;
		r[fy] = (r[x]-r[y]+z+2)%2;
	}	
}
int main()
{
        freopen("trueliars.in","r",stdin);
    freopen("trueliars.out","w",stdout);
	int n,p,q;
	while(cin >> n >> p >> q && (n | p | q)){
		int m = p+q;
		clear_set();
		for(int i = 0;i < n;i++){
			char str[5];
			int x,y,z = 0;					
			scanf("%d%d%s",&x,&y,str);
			if(str[0] == 'n')	z = 1;			
			union_set(x,y,z);
		} 
		int tot = 0;
		for(int i = 1;i <= m;i++){
			if(find_set(i) == i){
				f[++tot] = i;					
				for(int j = 1;j <= m;j++){
					if(find_set(j) == i){
						a[tot][r[j]]++;		 
					}
				}
			}
		}
		dp[0][0] = 1;
		for(int i = 1;i <= tot;i++){			
			for(int j = p;j >= 0;j--){	
			     if(j >= a[i][0])
				dp[i][j] += dp[i-1][j-a[i][0]];	
				if(j >= a[i][1])
                dp[i][j] += dp[i-1][j-a[i][1]];	 
			}
				
		}
		if(dp[tot][p] != 1){
			printf("no\n");
			continue;
		}
		int t = p;
		for(int i = tot;i >= 1;i--){
			if(dp[i-1][t-a[i][0]] == 1){
				for(int j = 1;j <= p+q;j++){
					if(find_set(j) == f[i] && r[j] == 0){
						st.insert(j);
					}
				}
				t -= a[i][0]; 
			}
			else{
				for(int j = 1;j <= p+q;j++){
					if(find_set(j) == f[i] && r[j] == 1){
						st.insert(j);
					}
				}
				t -= a[i][1];
			}
		}
		set<int>::iterator ptr;
		for(ptr = st.begin();ptr != st.end();ptr++){
			printf("%d\n",*ptr);
		}
		printf("end\n");
	}
	return 0;
}