POJ 2912 Rochambeau(union-find-set)

Description

n个小伙伴进行猜拳游戏，除了裁判以外，其他人只会出单一的一种，给出m中猜拳的结果，要求找出裁判序号，并且输出在第几次猜拳可以确定。

Analyze

种类并查集、排除法做题

除了裁判的小伙伴分为3组：0、1、2

从1到n枚举，假设当前 i 是裁判，若合并除裁判外的其他人而无矛盾的话，i 是准裁判。记一下裁判的个数。

另外要确定最少几行可以得出”谁是裁判”结论，我们记录每次排除一个人时记下是哪一行出现了矛盾，得到n - 1个位置。因为排除了所有的非裁判才知道裁判是谁，所以那n - 1个位置中到最靠后一个位置才能排除n - 1个非裁判，才能得知谁是裁判。

Something

先来一个小总结：

种类并查集分两种：①种类2种②种类3种

(若是多于3种便不能由AB、AC的关系推出BC的关系)

“2种”还好写，”3种”的有固定的一套体系

而关于这套体系我还有些东西没弄清楚：

1. unite先if搞两者属于同一集合的情况（否则会WA）

2. 必须有else，把那里面的内容单独放外面会RE

3. 0= 、 1> 、2< 或者 0= 、1< 、2> 都是可行的

4. 关于(val[a] - val[b] + 3) % 3 != idx我觉得不能解释以下两种情况

①A > pre && B < pre -> A > B

②A < pre && B > pre -> A < B

现在明白了， A > pre && pre > B -> B > A!

这个大于号在这里很误导人，石头剪刀布是相互制约的！

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;

char ch[N * 4];
int n, m, a[N * 4], b[N * 4], pre[N], val[N];

int found(int x)
{
    if(pre[x] == -1)
        return x;
    int tem = found(pre[x]);
    val[x] += val[ pre[x] ];
    val[x] %= 3;
    return pre[x] = tem;
}

bool unite(int a, int b, int idx)
{
    int aa = found(a);
    int bb = found(b);
    if(aa == bb)/// == first, then != .
    {
        if((val[a] - val[b] + 3) % 3 != idx)
            return 1;
    }
    else
    {///without {} will be RE ! ? ? !
        pre[aa] = bb;
        val[aa] = (-val[a] + idx + val[b] + 3) % 3;
    }
    return 0;
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i = 1; i <= m; ++i)
            scanf("%d%c%d", &a[i], &ch[i], &b[i]);


        bool flag = 1;
        int idx, num = 0, cnt = 0, which = 0;
        for(int i = 0; i < n; ++i)///n times union-find-set
        {
            flag = 1;
            memset(val,  0, sizeof(val));
            memset(pre, -1, sizeof(pre));

            for(int j = 1; j <= m; ++j)
            {
                if(a[j] == i || b[j] == i)
                    continue;
                if(ch[j] == '=')
                    idx = 0;
                else if(ch[j] == '<')/// > is also OK ! ? ? !
                    idx = 1;
                else
                    idx = 2;
                if(unite(a[j], b[j], idx))
                {
                    flag = 0;
                    num = max(num, j);
                    break;
                }
            }

            if(flag)
                cnt++, which = i;
        }

        if(cnt == 0)
            cout << "Impossible" << '\n';
        else if(cnt > 1)
            cout << "Can not determine" << '\n';
        else
            printf("Player %d can be determined to be the judge after %d lines\n", which, num);
    }
    return 0;
}