POJ2912 Rochambeau（种类并查集）

Rochambeau

Time Limit: 5000MS	Memory Limit: 65536K
Total Submissions: 4313	Accepted: 1505

Description

N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

Input

Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 2,000) in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

Output

There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

Sample Input

Sample Output

Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

Source

Baidu Star 2006 Preliminary
Chen, Shixi (xreborner) living in http://fairyair.yeah.net/

链接

http://poj.org/problem?id=2912

题意

有n个小朋友玩减到石头布小游戏，其中有一个裁判，剩余的人分为三组。规则是：裁判可以出石头剪刀布三种手势里边的任意一种，而同一组的人只能出一样的手势。给定n和m组游戏结果，问你能不能找出裁判，如果能，问谁是裁判以及经过多少组才能判断出来。

题解

这道题和POJ1182 食物链很像，也是三种关系，稍微复杂些。我们可以这样处理，枚举每一个人当裁判的时候，游戏结果会不会发生冲突，如果不冲突，说明这个人可以当裁判。裁判的数量只有一个才符合规则，超过一个则输出无法判断，一个都没有则输出不可能。

注意：当i作为裁判时，他参与的比赛需要跳过，因为他可以出任意手势。其余的按照食物链情况进行处理就行。pos[i] = j + 1表示当第i个人作为裁判时出现矛盾的位置，当某个人作为裁判时，他应该需要经过“max(pos)”组才能判断出来，即前面的n-1人当裁判时都是错误的。

参考了acm_cxlove的题解和focus_best的题解。

代码

Status	Accepted
Time	500ms
Memory	748kB
Length	2567

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 2010;
int F[maxn];
int rel[maxn];
int pos[maxn];

struct Node
{
    int l, r, k;
}a[maxn];

int find(int x)
{
    if (x == F[x])
        return x;
    int tmp = find(F[x]);
    rel[x] = (rel[x] + rel[F[x]]) % 3;
    F[x] = tmp;
    return F[x];
}

void init(int n)
{
    for (int i = 0; i <= n; ++i)
    {
        F[i] = i;
        rel[i] = 0;
    }
}

int main()
{
    int n, m, x, y;
    int rootx, rooty;
    char ch;
    while (scanf("%d%d", &n, &m) == 2)
    {
        int ans = 0;
        for (int i = 0; i < m; ++i)
        {
            cin >> a[i].l >> ch >> a[i].r;
            x = a[i].l, y = a[i].r;
            if (ch == '=')
                a[i].k = 0;
            else if (ch == '>')
                a[i].k = 1;
            else if (ch == '<')
                a[i].k = 2;
        }
        memset(pos, -1, sizeof(pos));
        for (int i = 0; i < n; ++i)
        {
            init(n); // 每枚举一次都需要进行初始化
            for (int j = 0; j < m; ++j)
            {
                if (i == a[j].l || i == a[j].r) // i参与的比赛需要跳过
                    continue;
                rootx = find(a[j].l), rooty = find(a[j].r);
                if (rootx != rooty)
                {
                    F[rooty] = rootx; // 合并
                    rel[rooty] = (rel[a[j].l] + 3 -rel[a[j].r] + a[j].k) % 3;
                }
                else // 判断
                {
                    if (a[j].k == 0 && rel[a[j].l] != rel[a[j].r])
                    {
                        pos[i] = j + 1;
                        break;
                    }
                    if (a[j].k == 1 && (3 - rel[a[j].l] + rel[a[j].r]) % 3 != 1)
                    {
                        pos[i] = j + 1;
                        break;
                    }
                    if (a[j].k == 2 && (3 - rel[a[j].l] + rel[a[j].r]) % 3 != 2)
                    {
                        pos[i] = j + 1;
                        break;
                    }
                }
            }
        }
        int cnt = 0;
        x = 0, y = 0;
        for (int i = 0; i < n; ++i)
        {
            if (pos[i] == -1)
            {
                cnt++;
                x = i;
            }
            y = max(y, pos[i]);
        }
        if (cnt == 0) // 没有人可以当裁判
            printf("Impossible\n");
        else if (cnt > 1) // 可以当裁判的人超过一个
            printf("Can not determine\n");
        else
            printf("Player %d can be determined to be the judge after %d lines\n", x, y);
    }
    return 0;
}

其中判断部分可以进行简化。

if ((3 - rel[a[j].l] + rel[a[j].r]) % 3 != a[j].k)
{
    pos[i] = j + 1;
    break;
}

食物链的变形题还是挺多的，核心都是合并与查找时候的向量关系。

The end.
2018-04-21 星期六