K - Rochambeau - poj2912（类似食物链）

一群小孩玩一个简单石头布布游戏，这些小孩会分成三组（组内可能没有人）+一个自由人（比翻译成裁判合理多了），同一组的小孩只会出同一种手势（不会变的），不过裁判可以出任意的手势，这些小孩能就会相互猜拳玩，A>B代表A赢B， <代表输， =代表平了，给你这些小孩玩游戏的结果，问你能不能找到那个自由人，如果找不出来，就输出Can not determine，如果发现不可能有这样的结果，除非有不止一个自由者那就输出Impossible，如果就一个自由者，那就输出这个自由者，和最先能判断这个自由者的位置的行号。。。

///////////////////////////////////

跟食物链差不多，查找自由者可以枚举每个人，比较简单就不说了

#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<queue>

#include<stack>

using namespace std;

const int maxn = ;

int f[maxn], val[maxn];

//0代表同类， 1代表赢， 2代表输

struct node{int u, v, rel;}data[maxn*];

int Find(int x)

{

    int k = f[x];

    if(f[x] != x)

    {

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

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

    }

    return f[x];

}

//如果k是裁判是否有矛盾产生，有返回产生矛盾的行数， 没有返回-1

int Solve(int k, int N, int M)

{//这里跟食物链一样的

    int i, u, v, ru, rv;

    for(i=; i<N; i++)

        f[i] = i, val[i]=;

    for(i=; i<M; i++)

    {

        u = data[i].u, v = data[i].v;

        if(u != k && v != k)

        {

            ru = Find(u), rv = Find(v);

            if(ru == rv && (val[v]+data[i].rel)% != val[u] )

                return i;

            f[ru] = rv;

            val[ru] = (data[i].rel-val[u]+val[v]+)%;

        }

    }

    return -;

}

int main()

{

    int i, N, M;

    while(scanf("%d%d", &N, &M) != EOF)

    {

        char ch;

        for(i=; i<M; i++)

        {

            scanf("%d%c%d", &data[i].u, &ch, &data[i].v);

            if(ch == '=')

                data[i].rel = ;

            else if(ch == '>')

                data[i].rel = ;

            else

                data[i].rel = ;

        }

        int p = Solve(-, N, M);

        

        //没有矛盾产生，无法判断出谁是裁判

        if(N !=  && p == -)

            printf("Can not determine\n");

        else if(N == )//只有一个人，只能是裁判

            printf("Player 0 can be determined to be the judge after 0 lines\n");

        else

        {

            int k=, q, j;//k记录有多少个可以担任裁判

            for(i=; i<N; i++)

            {

                j = Solve(i, N, M);

                if(j == -)

                    k++, q = i;

                else

                    p = max(p, j);//因为要求可以最近的看出裁判的地方，其实就是别的点产生矛盾最远的地方

                if(k > )

                    break;

            }

            if(k == )

                printf("Impossible\n");

            else if(k > )

                printf("Can not determine\n");

            else

                printf("Player %d can be determined to be the judge after %d lines\n", q, p+);

        }

    }

    return ;

}

巴特西

K - Rochambeau - poj2912（类似食物链）

最新文章

热门文章