首页 > 代码库 > 1811 Rank of Tetris
1811 Rank of Tetris
【原题】
http://acm.hdu.edu.cn/showproblem.php?pid=1811
【类型】
并查集+拓扑排序
【题意】
给定一些点对之间的关系（大于小于相等），判断是否发生冲突。
【分析】
对于冲突判断，直观的想法就是拓扑排序。以大于号或者小于号方向作为拓扑序的方向，如果处理时出现违反拓扑序列的情况则可判断为冲突。
然后这道题还有另外一个问题就是相等情况的处理，如果直接按照拓扑排序对其进行分析，则可能发生错误。为了解决这个问题，可以用并查集进行预处理，将所有相等的点缩成1个点，然后进行后序的拓扑排序。
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int father[10001]; void clean_father(int n){ for (int i=0;i<n;i++) father[i]=i;} int getfather(int x){ if (father[x]!=x) father[x]=getfather(father[x]); return father[x];}void link(int x,int y){ father[getfather(x)]=getfather(y);} int x[20001],y[20001],rd[10001],num[10001],start[10001];char z[20001];typedef struct { int a,b;} node;node a[20001];bool op(node a,node b){ return a.a<b.a;}int stack[10001];int main(){ int n,m; while (scanf("%d%d",&n,&m)!=EOF) { clean_father(n); for (int i=1;i<=m;i++) { scanf("%d %c %d",&x[i],&z[i],&y[i]); if (z[i]==‘=‘) link(x[i],y[i]); } int tail=0; for (int i=0;i<n;i++) rd[i]=-1; int tot=0; for (int i=0;i<n;i++) { rd[getfather(i)]=0; if (rd[i]==0) tot++; } for (int i=1;i<=m;i++) switch(z[i]) { case ‘>‘: tail++; a[tail].a=getfather(x[i]); a[tail].b=getfather(y[i]); rd[getfather(y[i])]++; break; case ‘<‘: tail++; a[tail].a=getfather(y[i]); a[tail].b=getfather(x[i]); rd[getfather(x[i])]++; } sort(&a[1],&a[tail+1],op); int o=-1; for (int i=0;i<n;i++) num[i]=0; for (int i=1;i<=tail;i++) { if (a[i].a!=o) { o=a[i].a; start[o]=i; } num[o]++; } int top=0; for (int i=0;i<n;i++) if (rd[i]==0) { top++; stack[top]=i; } if (top==0) { printf("CONFLICT\n"); continue; } bool flag=false,done=false; while (top>0&&(!done)) { if (top>1) flag=true; int now=stack[top]; top--;tot--; for (int i=0;i<num[now];i++) { rd[a[start[now]+i].b]--; if (rd[a[start[now]+i].b]==0) { top++; stack[top]=a[start[now]+i].b; } else if (rd[a[start[now]+i].b]<0) { done=true; break; } } num[now]=0; } if (tot>0||done) printf("CONFLICT\n"); else if (flag) printf("UNCERTAIN\n"); else printf("OK\n"); } return 0;}
1811 Rank of Tetris
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。