算法ACMPOJ 1417 True Liars
xucanxx参考自大佬的博客：https://blog.csdn.net/gg_gogoing/article/details/38753567
题目
题面
一个岛上有神与恶魔两个种族，神会说真话，恶魔会说假话。已知神与恶魔的个数，但不知道具体个人是属于哪个。
n,x,y
这个人问n次 ，x为神的个数，y为恶魔的个数。
每次的问题为 xi,yi,a 问xi ,yi是否为神？ a为yes/no。注意xi,yi可能为同一个人
若最终可得出哪些是神则从小到大输出神的编号，并最终输出end
否则输出no
输入格式如下：
1
2
3
4
5
6
7
| n p1 p2
xl yl a1
x2 y2 a2
...
xi yi ai
...
xn yn an
|
第一行有三个非负整数 n, p1, 和 p2. n 是 Akira 问的问题数. p1 和 p2 是在传说中记载的神族和恶魔族的人口数量。下面的每 n 行包括两个整数xi, yi和一个单词 ai。 xi 和 yi 是每个人的编号，号码范围从 1 到 p1 + p2。 ai 可能是 yes 或者 no。如果居民 xi 想让你认为 yi 是神族，他会回答 yes。注意：xi 和 yi 可能相同。所以”你是神族吗？“是一个有效的问题。还要注意，Akira 十分紧张，所以相同的问题可能重复出现。
数据范围：
n ＜ 1000
p1,p2 < 300
出现 0 0 0 的一行标示数据结束。 数据保证成立，没有矛盾数据。
Output
对于每个数据集，如果它包含足够的信息来对所有居民进行分类，则按升序打印所有神族居民的编号，一行一个。 在输出数字后再输出end。 如果给定数据集不包括足以识别所有神族的信息，输出no。
Examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 2 1 1
1 2 no
2 1 no
3 2 1
1 1 yes
2 2 yes
3 3 yes
2 2 1
1 2 yes
2 3 no
5 4 3
1 2 yes
1 3 no
4 5 yes
5 6 yes
6 7 no
0 0 0
|
Output
1
2
3
4
5
6
7
8
9
10
| no
no
1
2
end
3
4
5
6
end
|
思路
经过简单的推理可得只要说了‘yes’那么那两个就属于同一类，‘no’则相反
使用并查集表名它们的关系，用背包统计在不同情况下有多少种答案。
最后进行答案统计。
代码
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
| #include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int pr[1010], relation[1010];
int kind[1010], cnt[2010], dp[1010][1010];
int p[1010][1010];
int x, y, z;
int ans[1010], f;
int find(int xx)
{
if (pr[xx] == -1)
{
return xx;
}
int tmp = find(pr[xx]);
relation[xx] = (relation[xx] + relation[pr[xx]]) % 2;
pr[xx] = tmp;
return tmp;
}
int solve()
{
memset(dp, 0, sizeof(dp));
memset(p, 0, sizeof(p));
memset(cnt, 0, sizeof(cnt));
f = 0;
int k = 0;
for (int i = 1; i <= x + y; i++)
find(i);
for (int i = 1; i <= x + y; i++)
{
if (pr[i] == -1)
kind[k++] = i;
}
for (int i = 0; i < k; i++)
{
cnt[i * 2] = 1;
for (int j = 1; j <= x + y; j++)
{
if (pr[j] == kind[i])
{
if (relation[j] == 0)
cnt[i * 2]++;
else
cnt[i * 2 + 1]++;
}
}
}
dp[0][cnt[0]]++; p[0][cnt[0]] = 0;
dp[0][cnt[1]]++; p[0][cnt[1]] = 1;
for (int i = 1; i < k; i++)
for (int j = x; j >= 0; j--)
{
if (j >= cnt[2 * i] && dp[i - 1][j - cnt[2 * i]] )
{
dp[i][j] += dp[i - 1][j - cnt[2 * i]];
p[i][j] = 0;
}
if (j >= cnt[2 * i + 1] && dp[i - 1][j - cnt[2 * i + 1]] )
{
dp[i][j] += dp[i - 1][j - cnt[2 * i + 1]];
p[i][j] = 1;
}
}
if (dp[k - 1][x] != 1)
return 0;
int m = x, t;
f = 0;
for (int i = k - 1; i >= 0; i--)
{
if (p[i][m] == 0)
{
t = 0; m = m - cnt[i * 2];
}
else
{
t = 1; m = m - cnt[2 * i + 1];
}
for (int j = 1; j <= x + y; j++)
{
if (pr[j] == kind[i] || j == kind[i])
{
if (relation[j] == t)
ans[f++]=j;
}
}
}
sort(ans, ans + f);
return 1;
}
int main()
{
while (cin >> z >> x >> y)
{
if (x == 0 && y == 0 && z == 0)
break;
memset(pr, -1, sizeof(pr));
memset(relation, 0, sizeof(relation));
for (int i = 0; i < z; i++)
{
int a, b;
char s[10];
cin >> a >> b >> s;
if (a < b)
{
int tmp = a; a = b; b = tmp;
}
int aa = find(a), bb = find(b);
if (aa == bb)
{
continue;
}
if (s[0] == 'y')
{
pr[aa] = bb;
relation[aa] = (relation[a] + relation[b]) % 2;
}
else
{
pr[aa] = bb;
relation[aa] = (relation[a] + relation[b] + 1) % 2;
}
}
if (x == y)
{
cout<<"no"<<endl; continue;
}
if (solve())
{
for (int i = 0; i < f; i++)
{
cout << ans[i]<<endl;
}
cout << "end" << endl;
}
else
cout << "no" << endl;
}
return 0;
}
|
