链接
http://poj.org/problem?id=1417
题意
有 $p$ 个好人，$q$ 个坏人
$n$ 次询问，问 $x$：$y$是好人还是坏人
如果 $x$ 是好人，那么他会如实回答，否则他会撒谎
求能否唯一确定哪些人是好人
思路
如果回答是 “yes”，那么 $x,y$ 都是好人或者都是坏人
如果回答是 “no”，那么 $x,y$ 一个是好人一个是坏人
如果两个人不在一个集合里，那么把两个集合合并，并用边带权并查集维护关系
再根据每个集合内的关系把每个集合分成两个子集，每个子集里的人都是一类人，但现在还不能确定哪类是好人
记 $dp[i][j]$ 为前 $i$ 个集合凑 $j$ 个好人的方案，$sz[i][0],sz[i][1]$ 为第 $i$ 个集合两个子集的大小
转移方程：$dp[i][j]=dp[i-1][j-sz[i][0]]+dp[i-1][j-sz[i][1]]$
在转移过程中用一个数组记录是从哪转移过来的
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<climits>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=605;
int n,p,q,fa[N],w[N],dp[N][N],pre[N][N];
bool st[N];
VI v[N][2];
int find(int x) {
if(x==fa[x]) return x;
int root=find(fa[x]);
w[x]^=w[fa[x]];
return fa[x]=root;
}
int main() {
while(~scanf("%d%d%d",&n,&p,&q)) {
if(n==0&&p==0&&q==0) break;
for(int i=1;i<=p+q;i++) {
fa[i]=i;
w[i]=0;
}
for(int i=1;i<=n;i++) {
int x,y;
char s[5];
scanf("%d%d%s",&x,&y,s);
int tx=find(x),ty=find(y);
int temp=s[0]=='y'?0:1;
if(tx!=ty) {
fa[tx]=ty;
w[tx]=(w[y]+w[x]+temp)&1;
}
}
int cnt=0;
memset(st,false,sizeof st);
for(int i=1;i<=p+q;i++) {
if(st[i]) continue;
int root=find(i);
++cnt;
for(int j=i;j<=p+q;j++) {
if(!st[j]&&find(j)==root) {
v[cnt][w[j]].PB(j);
st[j]=true;
}
}
}
memset(dp,0,sizeof dp);
dp[0][0]=1;
for(int i=1;i<=cnt;i++) {
for(int j=p;j>=0;j--) {
if(j-SZ(v[i][0])>=0&&dp[i-1][j-SZ(v[i][0])]) {
dp[i][j]+=dp[i-1][j-SZ(v[i][0])];
pre[i][j]=j-SZ(v[i][0]);
}
if(j-SZ(v[i][1])>=0&&dp[i-1][j-SZ(v[i][1])]) {
dp[i][j]+=dp[i-1][j-SZ(v[i][1])];
pre[i][j]=j-SZ(v[i][1]);
}
}
}
if(dp[cnt][p]!=1) {
puts("no");
} else {
VI res;
for(int i=cnt,j=p;i>=1;j=pre[i][j],i--) {
if(j-pre[i][j]==SZ(v[i][0])) {
for(int k=0;k<SZ(v[i][0]);k++) {
res.PB(v[i][0][k]);
}
} else {
for(int k=0;k<SZ(v[i][1]);k++) {
res.PB(v[i][1][k]);
}
}
}
sort(ALL(res));
for(int i=0;i<SZ(res);i++) {
printf("%d\n",res[i]);
}
puts("end");
}
for(int i=1;i<=cnt;i++) {
v[i][0].clear();
v[i][1].clear();
}
}
return 0;
}
|