自动搬运

查看原文

来自洛谷，原作者为

	lym2022 这个人很勤快，但不想留下什么

搬运于2025-08-24 23:00:16，当前版本为作者最后更新于2025-04-02 16:15:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

现在有 $p1$ 个天神和 $p2$ 个恶魔，天使说真话，恶魔说假话，共有 $n$ 条信息，第 $i$ 条信息表示问编号为 $x_i$ 的人 $y_i$ 是否是天神，问全部的人中有几个是天神

思路

可以先从条件入手，当 $x_i$ 回答 yes 时，如果 $x_i$ 是神那么 $y_i$ 为神，如果 $x_i$ 是恶魔那么 $y_i$ 也为恶魔；当 $x_i$ 回答 no 时，如果 $x_i$ 是神那么 $y_i$ 为恶魔，如果 $x_i$ 是恶魔那么 $y_i$ 为神。

我们发现 $x_i$ 回答 yes 时 $x_i$ 和 $y_i$ 同族，反之异族，有种并查集得感觉。考虑用带权并查集（扩展域不好写）。

设数组 $v$ 表示节点 $i$ 和根节点的关系，如果 $v_i$ 为 $0$，表示 $i$ 和根节点同族，反之异族，这样设的好处在于可以用异或来更新 $i$ 的孩子与根节点的关系。

在输入时如果为 yes 那么两点同族，合并时传递一个值，表示是否相同，如果相同那么异或 $1$，否则异或 $0$。接着记录每个点所属的集合，每个集合中与根节点同族的节点数量和异族的节点数量。

由于我们确定的只是集合中各点与根的关系，因此并不能判断集合中与根同种的还是不同种的节点是神。所以我们可以进行背包 dp。$f[i][j]$ 表示已经从前 $i$ 个集合中选取了 $j$ 个人当神的方案数，然后看是否能凑出从前 $tot$ 个集合中凑出 $p1$ 个神就好了，由于他让判断接是否唯一，所以只要看 $f[tot][p1]$ 是否等于 $1$ 就好了。

code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

bool flag = true;

int n,que,angel,demon,f[N][N],bel[N],sm[N][2],fa[N],tot;
 
//n为总共人数，que为条件数，angel为天神数，demon为恶魔数，f为dp数组，bel为节点所属集合，sm为与根节点的关系，第二维 0为相同，1为不同，fa为并查集数组，tot为集合数量 

bool vis[N][2],v[N];

//vis为第 i 个集合中与根节点相同的点选，还是与根节点不同的点选，v为与根节点得关系，0为同族，1为异族 

int find(int x) {              //查询根节点并更新关系 
	if(fa[x] != x) {
		int fax = fa[x];
		fa[x] = find(fa[x]);
		v[x] = v[x] ^ v[fax];
	}
	return fa[x];
}

void unionn(int x,int y,int t) {   //合并两个集合并重新确定关系 
	int xx = find(x);
	int yy = find(y);
	if(xx == yy) return;
	fa[xx] = yy;
	v[xx] = v[x] ^ v[y] ^ t;
}

void init() {                      //初始化 
	n = angel + demon,tot = 0;
	for(int i = 1;i<=n;i++) bel[i] = v[i] = 0;
	for(int i = 1;i<=n;i++) fa[i] = i;
	for(int i = 1;i<=n;i++) for(int j = 0;j<=1;j++) sm[i][j] = vis[i][j] = 0;
	for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) f[i][j] = 0;
}

void solve() {
	cin >> que >> angel >> demon;
	if(que == 0 && angel == 0 && demon == 0) { 
		flag = false;
		return;
	}
	init();
	while(que--) {
		int x,y;
		string op;
		cin >> x >> y >> op;
		if(op == "yes") unionn(x,y,0);            //同族合并 
		else unionn(x,y,1);                       //异族合并 
	}
	for(int i = 1;i<=n;i++) if(find(i) == i) bel[i] = ++tot;        //如果自己为根节点，那么将自己所属的集合编号设为 ++tot (tot为已经存在集合数） 
	for(int i = 1;i<=n;i++) sm[bel[find(i)]][v[i]]++;               //传递 
	f[0][0] = 1;                       //一定要初始化！！！
	for(int i = 1;i<=tot;i++) {
		for(int j = 0;j<=angel;j++) {
			if(j >= sm[i][0]) f[i][j] += f[i-1][j-sm[i][0]];        //如果与根节点同族结点个数能放得下，那么累加方案 
			if(j >= sm[i][1]) f[i][j] += f[i-1][j-sm[i][1]];        //如果与根节点异族结点个数能放得下，那么累加方案 
		}
	}
	if(f[tot][angel] != 1) {         //如果最终的方案数不是 1，那么无解 
		cout << "no\n";
		return;
	}
	for(int i = tot;i>=1;i--) {
		if(f[i-1][angel-sm[i][0]] == 1) {   //f[tot][angel] 是由状态 f[tot-1][angel-cnt[i][0/1]]转来的，又由于 f[tot][angel] == 1，
			angel -= sm[i][0];              //也就是说 f[tot-1][angel-sm[i][0]]和 f[tot-1][angel-sm[i][1]] 中,一定是 一个所存方案书数为 1, 另一个所存方案数为 0,因为只有这样,才能保证 f[tot][angel] 等于 1。 
			vis[i][0] = true;               //如果 f[tot-1][angel-sm[i][0]] == 1,那么说明在集合 i 中我选的是与根节点同族的节点当作神;
		}else {                             //如果 f[tot-1][angel-sm[i][1]] == 1, 那么说明在集合 i 中我选的是与根节点【不同】的节点当作神。 
			angel -= sm[i][1];              //我们只需要用一个 vis[i][0/1] 数组记录,
			vis[i][1] = true;               //记录在集合 i 中我用的是哪个种类。 
		}
	}
	for(int i = 1;i<=n;i++) if(vis[bel[find(i)]][v[i]]) cout << i << '\n';          //每个节点所属的集合是否用的是与这个节点种类相同的节点，是就输出 
	cout << "end\n";             //不要忘了输出end 
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(flag) solve();
	return 0;
}

这是本 xxs 的第二篇题解，不喜勿喷