题意：有两种人，一种人只会说真话，另一种人只会说假话。只会说真话的人有p1个，另一种人有p2个。给出m个指令，每个指令为a b yes/no，意思是，如果为yes，a说b是只说真话的人，如果为no，a说b是只说假话的人。注意，a可以为b。保证每个指令都是正确的，且相互之间不矛盾。问，能不能确定哪些人是说真话的人，如果能，输出所有只说真话的人；如果不能，输出no。
解法：首先，用并查集建树，每个节点有两个参数，f和r，f表示父亲节点的编号，r表示与父亲节点是不是同一种人。r为0表示该节点与父亲节点是一种人，r为1表示该节点与父亲节点不是一种人。则用并查集处理之后，就可以分为k棵树，每棵树上可能有x[i]个人是同一种人，y[i]个是另一种人，(不确定哪个是说真话人的数量，哪个是说假话的人的数量)，且每棵树之间互不影响。所以即是一个背包问题，用dp解决即可。
tag:并查集，DP，背包
/*
* Author: Plumrain
* Created Time: 2013-11-28 10:26
* File Name: DS-POJ-1417.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define CLR1(x) memset(x, -1, sizeof(x))
#define PB push_back
typedef pair<int, int> pii; struct oo{
int a, b, pos;
void clr(){
a = ; b = ;
}
}; struct node{
int f, r;
}; node p[];
pii num[];
vector<int> ans;
oo cnt[];
map<int, int> mp;
int n, m, p1, p2, d[][]; int find(int x)
{
if (x != p[x].f){
int y = p[x].f;
p[x].f = find(p[x].f);
p[x].r = (p[x].r + p[y].r) % ;
}
return p[x].f;
} void merge(int a, int b, int x, int t1, int t2)
{
p[t1].f = t2;
p[t1].r = (p[a].r + p[b].r + x) % ;
} void init()
{
for (int i = ; i <= n; ++ i)
cnt[i].clr(); for (int i = ; i <= n; ++ i){
p[i].f = i;
p[i].r = ;
} int a, b, x;
char s[];
for (int i = ; i < m; ++ i){
scanf ("%d%d%s", &a, &b, s);
if (s[] == 'y') x = ;
else x = ; int t1 = find(a), t2 = find(b);
if (t1 != t2)
merge(a, b, x, t1, t2);
}
} void gao0()
{
if (p2 == || p1 == ){
for (int i = ; i <= p1; ++ i)
printf ("%d\n", i);
printf ("end\n");
return;
}
printf ("no\n");
} int main()
{
while (scanf ("%d%d%d", &m, &p1, &p2) != EOF){
if (!m && !p1 && !p2) break; if (!m){
gao0();
continue;
} n = p1 + p2;
init(); if (p1 == p2){
printf ("no\n");
continue;
} CLR (num);
for (int i = ; i <= n; ++ i){
int y = find(i);
if (!p[i].r) ++ num[y].first;
else ++ num[y].second;
} int all = ;
for (int i = ; i <= n; ++ i)
if (num[i].first + num[i].second){
cnt[all].a = num[i].first;
cnt[all].b = num[i].second;
cnt[all].pos = i;
++ all;
} CLR1 (d);
d[][] = ;
for (int i = ; i < all; ++ i)
for (int j = ; j <= p1; ++ j){
if (j >= cnt[i].a && d[i-][j-cnt[i].a] >= ){
if (d[i][j] == -) d[i][j] = ;
d[i][j] += d[i-][j-cnt[i].a];
}
if (j >= cnt[i].b && d[i-][j-cnt[i].b] >= ){
if (d[i][j] == -) d[i][j] = ;
d[i][j] += d[i-][j-cnt[i].b];
}
} if (d[all-][p1] != ) printf ("no\n");
else{
int j = p1;
mp.clear();
for (int i = all-; i; -- i){
if (j >= cnt[i].a && d[i-][j-cnt[i].a] == ){
j -= cnt[i].a;
mp[cnt[i].pos] = ;
}
else if (j >= cnt[i].b && d[i-][j-cnt[i].b] == ){
j -= cnt[i].b;
mp[cnt[i].pos] = ;
}
} ans.clear();
for (int i = ; i <= n; ++ i){
int y = find(i);
if (mp.count(y) && mp[y] == p[i].r)
ans.PB (i);
} sort(ans.begin(), ans.end());
int sz = ans.size();
for (int i = ; i < sz; ++ i)
printf ("%d\n", ans[i]);
printf ("end\n");
} }
return ;
}