自动搬运

查看原文

来自洛谷，原作者为

	myxRUC **

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

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

以下是正文

思路

作为经典的并查集问题，按照剪刀石头布分为三类，但是本题关键并不在于每个人属于哪一类，而是在于两个人的关系。这个关系我们可以用边权来记，由于规则分为平局和非平局，所以边权很容易用 $0、1$ 来表示。因此读入数据的时候我们把输赢统一为一种情况，赢者在后

for (int i = 1; i <= m; i++) {
	cin >> pl[i].a >> pl[i].c >> pl[i].b;
	if (pl[i].c == '>') {
		swap(pl[i].a, pl[i].b);//交换顺序
	}
}

所以对于每个人，先初始化，（$d$ 作为到达根节点的距离，很好的衡量两个人的胜负或者平局关系）

for (int i = 1; i <= n; i++)f[i] = i;
memset(d, 0, sizeof(d));//d表示到根节点的距离

当我们考虑每组数据的时候，由于 $N$ 不超过 $500$,不妨枚举每个人作为裁判，然后判断 $M$ 次游戏结果存不存在矛盾，（遇到裁判参与游戏就跳过，因为情况一定合理，裁判可以随意出），如果存在，说明这个人不是裁判；否则是裁判。

并查集函数

int dfs(int x) {
	if (x == f[x])return f[x];
	int t = dfs(f[x]);
	d[x] = d[x] + d[f[x]];
	return f[x] = t;
}

下面讨论对每局游戏的判断，假设是 $x1$ 和 $x2$，递归寻找 $x1$ 和 $x2$ 所属的集合，并根据 $x1$ 和 $x2$ 的关系确定距离 $dis$。

int x1=pl[i].a, x2=pl[i].b, dis = 0;
char c=pl[i].c;
if (x1 == k || x2 == k)continue;//裁判参与就不判断，因为一定不矛盾
int a = dfs(x1), b = dfs(x2);
if (c == '<'||pl[i].c=='>')dis = 1;
if (c == '=')dis = 0;

下面判断两种情况，就是两个人在不在一个集合以内

if (a == b)
{
      if (((d[x1] - d[x2]) % 3 + 3) % 3 != dis){
        ok = false;
        tp = min(tp, i);//记录判断裁判的位置
      }
}
else
{
      f[a] = b;
      d[a] = ((d[x2] - d[x1] + dis) % 3 + 3) % 3;
}

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 505, M = 2005;
int f[N], d[N];
int cnt = 0, n = 0, m = 0;
struct node {
	int a, b;
	char c;
}pl[M];
int dfs(int x) {
	if (x == f[x])return f[x];
	int t = dfs(f[x]);
	d[x] = d[x] + d[f[x]];
	return f[x] = t;
}
int main(void) {
	while (cin >> n >> m) {
		int cnt = 0, num = 0, tp = 0, pos = 0;
		if (n == 1 && m == 0) {
			num = 0, pos = 0;
		}
		for (int i = 1; i <= m; i++) {
			cin >> pl[i].a >> pl[i].c >> pl[i].b;
			if (pl[i].c == '>') {
				swap(pl[i].a, pl[i].b);
			}
		}
		for (int k = 0; k < n; k++) {
			tp = 2001;
			for (int i = 0; i < n; i++)f[i] = i;
			memset(d, 0, sizeof(d));
			bool ok = true;
			for (int i = 1; i <= m; i++) {
				int x1=pl[i].a, x2=pl[i].b, dis = 0;
				char c=pl[i].c;
				if (x1 == k || x2 == k)continue;
				int a = dfs(x1), b = dfs(x2);
				if (c == '<'||c=='>')dis = 1;
				if (c == '=')dis = 0;
				if (a == b) {
					if (((d[x1] - d[x2]) % 3 + 3) % 3 != dis) {
						ok = false;
						tp = min(tp, i);
					}
				}
				else {
					f[a] = b;
					d[a] = ((d[x2] - d[x1] + dis) % 3 + 3) % 3;
				}
			}
			if (tp == 2001) cnt++, num = k;
			else pos = max(pos, tp);
		}
		if (cnt == 0) {
			cout << "Impossible" << endl;
		}
		else if (cnt > 1) {
			cout << "Can not determine" << endl;
		}
		else {
			cout << "Player " << num << " can be determined to be the judge after " << pos << " lines\n";
		}
	}
	return 0;
}