题解：P10686 Rochambeau

myxRUC · 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;
}