Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 256 Accepted Submission(s): 110

Problem Description

自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。

为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排。

终于，Lele要开始行动了，对N个人进行排名。为了方便起见，每个人都已经被编号，分别从0到N-1,并且编号越大，RP就越高。
同时Lele从狗仔队里取得一些（M个）关于Rating的信息。这些信息可能有三种情况，分别是"A > B","A = B","A < B"，分别表示A的Rating高于B,等于B,小于B。

现在Lele并不是让你来帮他制作这个高手榜，他只是想知道，根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。
注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。

Input

本题目包含多组测试，请处理到文件结束。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系

Output

对于每组测试，在一行里按题目要求输出

Sample Input

Sample Output

OK

CONFLICT

UNCERTAIN

Author

linle

Source

HDOJ 2007 Summer Exercise（2）

Recommend

lcy

/*

yy了一天这个题的各种想法，最后看了题解才知道是拓扑排序，又看了一下拓扑排序；

拓扑排序：将一个图入度为零的点加入队列，如果多余一个，那么这个图不是树，很可能是森林，如果只有一个节点，

就进行删根操作，每删一个根就把这个根输出，删根时也将与之关联的边删掉

*/

#include<bits/stdc++.h>

#define N 20005

using namespace std;

vector<int >v[N];//构建邻接矩阵

int bin[N];//用于构建并查集

int in[N];//用于记录每个节点的入度

int n,m,sum;//节点数

char op[N][];

void inti()

{

    sum=n;

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

    {

        bin[i]=i;

        v[i].clear();

        in[i]=;

    }

}

int findx(int x)

{

    while(x!=bin[x])

        x=bin[x];

    return x;

}

int judge(int x,int y)

{

    int fx=findx(x);

    int fy=findx(y);

    if(fx!=fy)

    {

        bin[fx]=fy;

        return ;

    }

    return ;

}

void topoSort()

{

    queue<int >q;

    int i;

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

        if(in[i]==&&findx(i)==i)//入度为零的点（一棵树的根节点）

            q.push(i);

    int flag=;

    while(!q.empty())

    {

        if(q.size()>)//多于一个根节点就说明信息不完整

            flag=;

        int now=q.front();

        q.pop();

        sum--;

        for(i=;i<v[now].size();i++)

            if(--in[v[now][i]]==)//删根

                q.push(v[now][i]);//删根之后的子树根节点

    }

    if(sum>)

    {

        puts("CONFLICT");

    }

    else if(flag==)

    {

        puts("UNCERTAIN");

    }

    else

    {

        puts("OK");

    }

    return;

}

int x[N],y[N];

int main()

{

    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);

    //int c=0;

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

    {

        //if(c++==2)

        //    break;

        //cout<<"n="<<n<<" m="<<m<<endl;

        inti();

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

        {

            scanf("%d%s%d",&x[i],op[i],&y[i]);

            //cout<<x[i]<<" "<<op[i]<<" "<<y[i]<<endl;

            if(op[i][]=='=')

            {

                if(judge(x[i],y[i]))//两点不属于同一并查集

                {

                    sum--;

                }

            }

            getchar();

        }

        //cout<<endl;

        //break;

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

        {

            if(op[i][]!='=')

            {

                int fx=findx(x[i]);

                int fy=findx(y[i]);

                if(op[i][]=='>')

                {

                    v[fx].push_back(fy);

                    in[fy]++;

                }

                else

                {

                    v[fy].push_back(fx);

                    in[fx]++;

                }

            }

        }

        topoSort();

    }

    return ;

}

巴特西

Rank of Tetris

Rank of Tetris

最新文章

热门文章