ACM: hdu 1811 Rank of Tetris – 拓扑排序-并查集-离线

hdu 1811 Rank of Tetris

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

/*/
中文题：按照输入把给出的0~n-1排序，如果是'='按照大小排序，如果是'>'||'<'就按照符号排序；一开始也是被题意给欺骗了，就是这个'=' ，以为'='号的话两边的排序就按照大小，然后WA了一发。仔细思考之后发现，并不是这样的，例如 0 = 2 虽然按照排序是 2-0这样，但是这两个的值是相等的也就是说，这两个数要绑定到一起，在去和其他的数进行排序，这下题意就很清晰了：拓扑排序+并查集+离线。一开始把所有的'='连起来的点全部绑定起来，再用并查集和拓扑排序去排列，看是不是整个队列严格排序。这个写起来就很快了。我承认我犯傻，写到排序这里，本来应该去连接两个比较大小的队伍的根节点却忘了，搞得我重新写了几次真是【MDZZ】--真的只能剁手了、、、、下面有两组AC代码，一组用了ＳＴＬ　一组没用，都是ｚｚ惹的祸；AC代码：
/*/

#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"string"
#include"cstdio"
#include"vector"
#include"cmath"
#include"queue"
using namespace std;
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define MX 10005// 拓扑排序 + 并查集 + STL //因为思路差不多，注释只打在了第一个代码上面。//////////////////////////////////////////////////////////////////
/////////////////////////////queue////////////////////////////////
////////////////////////////////////////////////////////////////// struct Edge {
    int v,nxt;
} E[MX];
int p[MX];
int Head[MX],cnt;
int indegree[MX];
int n,m,st,ed,sum;int find(int x) {
    return p[x]==x?x:(p[x]=find(p[x]));
}int union_root(int a,int b) {
    a=find(a);
    b=find(b);
    if(a!=b) {　　　　
        p[b]=a;
        return 1;　　　　//返回是否进行了绑定操作
    }
    return 0;
}void init() {
    memset(Head,-1);
    memset(E,0);
    memset(indegree,0);
    for(int i=0; i<=n; i++) {
        p[i]=i;
    }
    cnt=0;
    sum=n;
}void edge_add(int st,int ed) {
    E[cnt].v=ed;
    E[cnt].nxt=Head[st];
    Head[st]=cnt++;
}void toposort() {      //几乎是模版。
    int information=1;
    queue<int>Q;
    while(!Q.empty())Q.pop();
    for(int i=0; i<n; i++) {
        if(!indegree[i]&&find(i)==i)  //入度为0，且是根节点
            Q.push(i);
    }
    while(!Q.empty()) {
        if(Q.size()>1)information=0;  //如果出现了多个入度为0的点说明没有严格排序，即信息不全，标记
        int a=Q.front();
        Q.pop();
        sum--;
        for(int i=Head[a]; ~i; i=E[i].nxt) {
            int v=E[i].v;
            indegree[v]--;
            if(!indegree[v]) { 　
                Q.push(v);
            }
        }
    }
    if(sum>0)printf("CONFLICT\n");   //出现了矛盾[环]就说明错了
    else if(!information)printf("UNCERTAIN\n");//信息不全
    else printf("OK\n");
}int main() {
    char B[MX];
    int A[MX],C[MX];
    while(~scanf("%d%d",&n,&m)) {
        init();
        for(int i=0; i<m; i++) {
            cin>>A[i]>>B[i]>>C[i];
            if(B[i]=='=') {
                if(union_root(A[i],C[i])) sum--;//绑定两个值相等的点，如果绑定了联通块数量 --；
            }
        }
        for(int i=0; i<m; i++) {
            if(B[i]=='=')continue;//这里要跳过已经绑定了的点
            if(B[i]=='>') {     //按照符号去排列大小
st=find(A[i]);
ed=find(C[i]);
} else {
st=find(C[i]);
ed=find(A[i]);
}
            edge_add(st,ed);
            indegree[ed]++;
        }
        toposort();
    }
    return 0;
}/////////////////////////////////////////////////////////////
///////////////////// vector + queue ////////////////////////
/////////////////////////////////////////////////////////////struct Edge {
int v,nxt;
} E[MX];
int p[MX];
int indegree[MX];
int n,m,st,ed,sum;vector<int >next_node[MX];int find(int x) {
return p[x]==x?x:(p[x]=find(p[x]));
}int union_root(int a,int b) {
a=find(a);
b=find(b);
if(a!=b) {
p[b]=a;
return 1;
}
return 0;
}void init(int n) {
memset(E,0);
memset(indegree,0);
for(int i=0; i<n; i++) {
next_node[i].clear();
p[i]=i;
}
sum=n;
}void toposort() {
int information=1;
queue<int>Q;
while(!Q.empty())Q.pop();
for(int i=0; i<n; i++) {
if(!indegree[i]&&find(i)==i)
Q.push(i);
}
while(!Q.empty()) {
if(Q.size()>1)information=0;
int a=Q.front();
Q.pop();
sum--;
        for(int i=0;i<next_node[a].size();i++)
        {
            if(--indegree[next_node[a][i]]==0)
            Q.push(next_node[a][i]);
        }
}
if(sum>0)printf("CONFLICT\n");
else if(!information)printf("UNCERTAIN\n");
else printf("OK\n");
}int main() {
char B[MX];
int A[MX],C[MX];
while(~scanf("%d%d",&n,&m)) {
init(n);
for(int i=0; i<m; i++) {
cin>>A[i]>>B[i]>>C[i];
if(B[i]=='=') {
if(union_root(A[i],C[i]))sum--;
}
}
for(int i=0; i<m; i++) {
if(B[i]=='=')continue;
if(B[i]=='>') {
st=find(A[i]);
ed=find(C[i]);
} else {
st=find(C[i]);
ed=find(A[i]);
}
            next_node[st].push_back(ed);
indegree[ed]++;
}
toposort();
}
return 0;
}

hdu 1811 Rank of Tetris

个人收藏笔记记录

开通VIP