Rochambeau---poj2912||zoj2751(并查集类似于食物链)

题目链接：http://poj.org/problem?id=2912 

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1751

题意：有n个人玩石头剪刀布，所以会产生石头>剪刀，剪刀>布，布>石头,所以就产生了和食物链那题一样的关系；

枚举＋关系并查集，枚举每个小孩为judge时的情况，若当前枚举情况下每个round都是正确的，则当前枚举编号可能是judge。

若只找到一个judge的可能，即为输出。若有多个就不确定了;

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <map>

#include <vector>

using namespace std;

typedef long long LL;

#define N 2520

#define met(a, b) memset(a, b, sizeof(a))

int f[N], r[N], wrong[N];

int Find(int x)

{

    int k = f[x];

    if(x!=f[x])

    {

        f[x] = Find(f[x]);

        r[x] = (r[x]+r[k])%;

    }

    return f[x];

}

struct node

{

    int x, y, op;

}a[N];

int main()

{

    int n, m;

    while(scanf("%d %d", &n, &m)!=EOF)

    {

        met(a, );

        for(int i=; i<=m; i++)

        {

            char ch;

            scanf("%d%c%d", &a[i].x, &ch, &a[i].y);

            if(ch == '=') a[i].op = ;

            if(ch == '>') a[i].op = ;

            if(ch == '<') a[i].op = ;

        }

        for(int i=; i<n; i++)///枚举裁判；

        {

            for(int j=; j<n; j++)

                f[j] = j, r[j] = ;

            wrong[i] = ;///第i个人当裁判的时候在哪产生矛盾；

            for(int j=; j<=m; j++)

            {

                if(a[j].x == i || a[j].y == i)continue;

                int x = a[j].x, y = a[j].y;

                int px = Find(x);

                int py = Find(y);

                if(px != py)

                {

                    f[px] = py;

                    r[px] = (r[y] + a[j].op - r[x] + )%;

                }

                else if(px == py && (r[y]+a[j].op)% != r[x])

                {

                    wrong[i] = j;

                    break;

                }

            }

        }

        int judge = , ans = , Index;

        for(int i=; i<n; i++)

        {

            if(wrong[i] == )

            {

                judge++;

                Index = i;

            }

            ans = max(wrong[i], ans);///当其他的情况矛盾了，那么就是确定结果的时候；

        }

        if(judge == ) printf("Player %d can be determined to be the judge after %d lines\n", Index, ans);

        else if(judge == ) printf("Impossible\n");///没有产生；

        else printf("Can not determine\n");///产生的不止一个，就是不确定；

    }

    return ;

}