首页 > 代码库 > HDU 1811 Rank of Tetris 并查集+拓扑排序
HDU 1811 Rank of Tetris 并查集+拓扑排序
题目来源:HDU 1811 Rank of Tetris
题意:中文
思路:一看就像用拓扑排序 不过多了等于号的情况 开始想之间把等于号按照RP改成大于号和小于号 后来发现 开始出现A=B 后来又出现 A<B 或A>B就矛盾了 没法判断了
用并查集把相等的看成一个点 相等的因为RP值不同 所以肯定有序 对于出现A=B 那么A和B的祖先相同 后来再出现A>B或A<B判断AB的祖先是否一样 最后等于号都处理掉了
剩下普通的拓扑排序了 排序的点当然是每个集合的祖先
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 10010; int a[maxn], d[maxn], f[maxn]; int n, m; struct edge { int u, v, next; }e[100010]; int s1[maxn], s2[maxn], op[maxn]; int first[maxn], cnt; void AddEdge(int u, int v) { e[cnt].v = v; e[cnt].next = first[u]; first[u] = cnt++; } int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } bool topo() { //puts("sdgs"); queue <int> Q; int sum = 0; for(int i = 0; i < n; i++) { int x = find(i); if(x == i) sum++; if(!d[x] && x == i) Q.push(x); } //printf("%d\n", sum); int flag = 0; while(!Q.empty()) { if(Q.size() > 1) flag = 1; int x = Q.front(); Q.pop(); sum--; for(int i = first[x]; i != -1; i = e[i].next) { int v = e[i].v; d[v]--; if(!d[v]) Q.push(v); } } if(sum) puts("CONFLICT"); else if(flag) puts("UNCERTAIN"); else puts("OK"); } int main() { while(scanf("%d %d", &n, &m) != EOF) { cnt = 0; memset(first, -1, sizeof(first)); memset(d, 0, sizeof(d)); for(int i = 0; i <= n; i++) f[i] = i; int flag = 0; for(int i = 1; i <= m; i++) { int u, v; char str1[100], str2[100], str3[100]; scanf("%s %s %s", str1, str3, str2); u = atoi(str1), v = atoi(str2); s1[i] = u; s2[i] = v; if(str3[0] == '=') op[i] = 0; else if(str3[0] == '>') op[i] = 1; else op[i] = 2; if(str3[0] != '=') continue; int x = find(u), y = find(v); if(x != y) { f[x] = y; } } for(int i = 1; i <= m; i++) { if(op[i] == 0) continue; int u = s1[i], v = s2[i]; int x = find(u), y = find(v); if(x == y) { flag = 1; break; } if(op[i] == 1) { d[y]++; AddEdge(x, y); } else { d[x]++; AddEdge(y, x); } } if(flag) puts("CONFLICT"); else topo(); } return 0; }
HDU 1811 Rank of Tetris 并查集+拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。