POJ 1417 True Liars

参考自大佬的博客：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  

Input

输入格式如下：

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

Input

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

no
no
1
2
end
3
4
5
6
end

思路

经过简单的推理可得只要说了‘yes’那么那两个就属于同一类，‘no’则相反
使用并查集表名它们的关系，用背包统计在不同情况下有多少种答案。
最后进行答案统计。

代码

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int pr[1010], relation[1010];
int kind[1010], cnt[2010], dp[1010][1010];//dp[i][j],代表一共i个头节点剩余容量为j时，一共有多少情况
int p[1010][1010];//p[i][j]代表一共i个头节点剩余容量为j时,在背包中的元素是不是与第i个头节点处于同一类
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]++;//记录与kind[i]的头节点有多少节点与它处于同一类
				else
					cnt[i * 2 + 1]++;//记录与kind[i]的头节点有多少节点不与它处于同一类
			}
		}
	}
	dp[0][cnt[0]]++; p[0][cnt[0]] = 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]] )//01背包
			{
				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)//看背包中的元素与第i个头节点同类还是相反
		{
			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()
{
	//freopen("F:/y.txt", "r", stdin);
	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())//f可能为0
		{
			for (int i = 0; i < f; i++)
			{
				cout << ans[i]<<endl;
			}
			cout << "end" << endl;
		}
		else
			cout << "no" << endl;
	}
	return 0;
}