首页 > 代码库 > HDU 1811 Rank of Tetris（拓扑排序+并查集）
HDU 1811 Rank of Tetris（拓扑排序+并查集）
http://acm.hdu.edu.cn/showproblem.php?pid=1811
题意：
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"。
为了更好的符合那些爱好者的喜好，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"。
思路：
这道题目需要注意的就是存在“=”的情况，存在等号的话就相当于这两个是一个整体了，他们中间不可能再插进去分数不同的人了，所以可以用并查集并在一起，然后统一用root来代替这一整个整体即可。
然后就是普通的拓扑排序了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 10000 + 5; 17 18 int n,m; 19 int pre_n; 20 int p[maxn]; 21 int vis[maxn]; 22 int degree[maxn]; 23 char c[2*maxn]; 24 int u[2*maxn],v[2*maxn]; 25 bool flag1,flag2; 26 vector<int> G[maxn]; 27 28 int Find(int x) 29 { 30 return p[x]==x?x:p[x]=Find(p[x]); 31 } 32 33 void tuopu() 34 { 35 memset(vis,0,sizeof(vis)); 36 for(int i=1;i<=n;i++) 37 { 38 int pos=-1; 39 int num=0; 40 for(int j=0;j<pre_n;j++) 41 { 42 int u=Find(j); 43 if(vis[u]!=i && degree[u]==0) 44 { 45 vis[u]=i; 46 pos=u; 47 num++; 48 } 49 } 50 if(num>1) flag1=true; 51 if(pos==-1) {flag2=true;return;} 52 degree[pos]=-1; 53 for(int j=0;j<G[pos].size();j++) 54 { 55 int v=G[pos][j]; 56 degree[v]--; 57 } 58 } 59 return; 60 } 61 62 int main() 63 { 64 //freopen("in.txt","r",stdin); 65 while(~scanf("%d%d",&n,&m)) 66 { 67 pre_n=n; 68 for(int i=0;i<n;i++) G[i].clear(); 69 memset(degree,0,sizeof(degree)); 70 for(int i=0;i<n;i++) p[i]=i; 71 72 for(int i=0;i<m;i++) 73 { 74 cin>>u[i]>>c[i]>>v[i]; 75 if(c[i]==‘=‘) 76 { 77 int x=Find(u[i]); 78 int y=Find(v[i]); 79 if(x!=y) 80 { 81 p[x]=y; 82 n--; 83 } 84 } 85 } 86 87 for(int i=0;i<m;i++) 88 { 89 int x=Find(u[i]); 90 int y=Find(v[i]); 91 if(c[i]==‘>‘) 92 { 93 G[x].push_back(y); 94 degree[y]++; 95 } 96 else if(c[i]==‘<‘) 97 { 98 G[y].push_back(x); 99 degree[x]++;100 }101 }102 103 flag1=flag2=false;104 tuopu();105 if(flag2) puts("CONFLICT");106 else if(flag1) puts("UNCERTAIN");107 else puts("OK");108 }109 return 0;110 }
HDU 1811 Rank of Tetris（拓扑排序+并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。