Peter有一个王国。在这个王国里，一共有2种人，即诚实人和撒谎人。诚实人永远说真话，撒谎人永远说假话。可惜的是，Peter只记得诚实人的数量和撒谎人的数量，但并不能确定每个人的身份。因此，他去民间收集了n组话语。每一组话语都是某人告诉Peter国王另一个人的身份。现在，Peter想知道能否根据这些话语推测出王国中所有人的唯一身份。 因为所有人分为了两类人：诚实 or 撒谎，所以很容易想到用并查集维护集合信息 但是具体谁是诚实的人无法判断出来 其次考虑要回溯出每一个诚实的人： 然后考虑带权并查集的细节： 这里比较迷惑的可能就是p[fx] = p[x] ^ p[y] ^ v; 我们可以举这样一个例子 剩下的就是正常的回溯和dp了True Liars
题目描述：
解题思路：
但是此时还有一个问题就是：
因为撒谎的人永远撒谎，诚实的人永远诚实，所以对于每一个集合我们只能大致的分出两类：
此时我们观察到诚实的人的数量是固定的，也就是说总有唯一的一种方式能够找出固定的诚实的人，所以考虑一个01背包，背包容量就是诚实的人的数量，最终如果能够保证f[m][m1] == 1(前m组集合中找到m1个诚实的人的方案唯一)，就说明ok，否则为不能
因为我们已经得知最后的状态，所以我们可以通过确定每一个人与其集合的父节点选择时（st[i]）是否属于同一状态（即是否与父类(st[i])相同）而确定是否是诚实的人
f[N] (父节点) p[N]（权值，表示是否为同一类）
int find(int x) {
if (x != f[x]) {
int u = find(f[x]);
p[x] ^= p[f[x]];//相同为0，不同为1
f[x] = u;
}
return f[x];
}
void merge(int x, int y, int v) {
int fx = find(x), fy = find(y);
if (fx != fy) {
f[fx] = fy;
p[fx] = p[x] ^ p[y] ^ v;
if (p[fx] == 1) //如果为不同类
{
sz[fy][0] += sz[fx][1];
sz[fy][1] += sz[fx][0];
} else//如果为同类
{
sz[fy][0] += sz[fx][0];
sz[fy][1] += sz[fx][1];
}
}
}
假设存在这么两组关系<A,B>,<C,D>
B与A为不同
D与C为相同
我们现在要merge(B,C,0)
那我们就需要将<A,B>合并到<C,D>上去，这时我们就考虑要改变p[A]使得B,D满足他们的关系为相同
那么这时只能让A与C的关系为不同，这样B,C的关系为相同
换成代码就是
p[A] = p[B] ^ p[D] ^ 0 == (1 ^ 0 ^ 0) = 1
dp的思路是，前N组人中找m1个诚实的人的方案数
代码实现：
# include<iostream>
# include<math.h>
# include<map>
# include<vector>
# include<algorithm>
using namespace std;
# define int long long
# define endl "\n"
const int N = 1005, mod = 998244353;
int n, m1, m2;
int p[1005], sz[1005][2], f[1005];
int dp[1005][1005];
bool st[1005];
int find(int x) {
if (x != f[x]) {
int u = find(f[x]);
p[x] ^= p[f[x]];
f[x] = u;
}
return f[x];
}
void merge(int x, int y, int v) {//合并
int fx = find(x), fy = find(y);
if (fx != fy) {
f[fx] = fy;
p[fx] = p[x] ^ p[y] ^ v;
if (p[fx] == 1) {
sz[fy][0] += sz[fx][1];
sz[fy][1] += sz[fx][0];
} else {
sz[fy][0] += sz[fx][0];
sz[fy][1] += sz[fx][1];
}
}
}
void solve() {
while (cin >> n >> m1 >> m2,n + m1 + m2 > 0) {
vector<int> a, b, c;
int len = m1 + m2;
for (int i = 1; i <= len; ++i) {
f[i] = i;
sz[i][0] = 1;
sz[i][1] = 0;
p[i] = 0;
st[i] = 0;
}
for (int i = 0; i < n; ++i) {
int x, y;
string op;
cin >> x >> y;
cin >> op;
if (op == "yes") {
merge(x, y, 0);
} else {
merge(x, y, 1);
}
}
for (int i = 1; i <= len; ++i) {
if (find(i) == i) {
a.push_back(sz[i][0]);
b.push_back(sz[i][1]);
c.push_back(i);
}
}
int m = a.size();
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= m1; ++j) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;//前0个人找0个诚实的人的方案为1
for (int i = 1; i <= m; ++i) {
for (int j = min(a[i - 1], b[i - 1]); j <= m1; ++j) {
dp[i][j] += dp[i - 1][j - a[i - 1]];
dp[i][j] += dp[i - 1][j - b[i - 1]];
}
}
if (dp[m][m1] != 1) {
cout << "no" << endl;
continue;
}
//回溯操作
for (int i = m, j = m1; i >= 1; --i) {
if (dp[i - 1][j - a[i - 1]]) {
st[c[i - 1]] = 0;
j -= a[i - 1];
} else if (dp[i - 1][j - b[i - 1]]) {
st[c[i - 1]] = 1;
j -= b[i - 1];
}
}
for (int i = 1; i <= len; ++i) {
int j = find(i);
if (p[i] == st[j]) {
cout << i << endl;
}
}
cout << "end" << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}