本文主要是介绍hud 1811 Rank of Tetris(拓扑排序+并查集+STL),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Rank of Tetris
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3671 Accepted Submission(s): 1026
为了更好的符合那些爱好者的喜好,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"。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行,分别表示这些关系
3 3 0 > 1 1 < 2 0 > 2 4 4 1 = 2 1 > 3 2 > 0 0 > 1 3 3 1 > 0 1 > 2 2 < 1
OK CONFLICT UNCERTAIN
一道很好的拓扑排序题,因为有等号的缘故,所以加大了难度。
题目数据量比较大,肯定不能用邻接矩阵来储存关系,会超内存,所以果断选择用领接表,然后用了一下午的时间学习了STL里面的vector。一开始没有考虑到连等的情况,所以没有用到并查集去合并‘=’,而是纯手动的读到‘=’就让两个点的入度相等(这样做完全行不通,不光出现1 = 2 = 3的情况回出错,1 > 2, 2 = 3, 4 > 3 的时候也会WA)后来引入并查集去处理等号以后就超时,经过很长时间的优化终于踩点过了,所以说有时候必要的学习时应该的。下面给出一些容易错的数据(仅供参考):
4 3
1 > 0
1 = 2
3 > 2
OK
5 4
1 > 0
1 = 2
2 = 3
3 < 4
OK
7 6
1 > 0
1 = 2
2 = 3
2 > 5
3 > 6
4 > 3
NUCERTAIN
我的解题思路:在读如数据的同时, 碰到‘=’时用并查集进行处理,(这点不好,这样由于‘=’的出现次序,数据要被重复合并多次),然后用模拟的方式去判断(这里没有用到一些技巧很惭愧),因为名次时确定的话每次只会有一个点的入度为0,如果同时有两个点的入度为0,说明名次不能被确定,如果有向图中出现环,说明冲突。(这里要注意的是条件不足时不能直接停止判断,因为后面还有可能出现错误)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;#define N 10005
#define INT vector<int>::iteratorint n, m, cnt, all, bir[N];
int rec[N * 2][2], vis[N], num[N];
vector<int> G[N];void handle(int a, int b){if (a == b)return;for (INT i = G[a].begin(); i != G[a].end(); i++)G[b].push_back(*i);num[a] = b;all++;
}int find(int x){return x != num[x]?num[x] = find(num[x]):x;
}int topo(int k, int sum){vis[k] = 1;int ok = 0;for (INT i = G[k].begin(); i != G[k].end(); i++){int a = find(*i);if (vis[a]) return -1;ok = topo(a, sum + 1);if (ok) return ok;}if (sum + all == n) return 1;vis[k] = 0;return 0;
}int main(){int a, b;char c;while (scanf("%d%d", &n, &m) != EOF){// Init.all = cnt = 0;memset(rec, 0, sizeof(rec));memset(bir, 0, sizeof(bir));for (int i = 0; i < n; i++)G[num[i] = i].clear();// Read.for (int i = 0; i < m; i++){scanf("%d %c %d", &a, &c, &b);if (c == '<')G[b].push_back(a);else if (c == '>')G[a].push_back(b);else{rec[cnt][0] = a;rec[cnt][1] = b;cnt++;}}// Handle.for (int i = 0; i < cnt; i++)handle(find(rec[i][0]), find(rec[i][1]));// Judge.int ok = 0;for (int i = 0; i < n; i++){a = find(i);if (bir[a]) continue;memset(vis, 0, sizeof(vis));ok = topo(a, 1);if (ok) break;bir[a] = 1;}if (ok == 1)printf("OK\n");else if (ok == -1)printf("CONFLICT\n");elseprintf("UNCERTAIN\n");}return 0;}
这是我研究了下别人的代码,然后结合自己代码优点写的,主要改了数据读入的地方,是在读取到‘=’时,先用并查集将两点合并(注意已经相等的点处理,对后面判断回有所影响),在所有数据都读取完毕后,在对‘<' 和‘>'进行处理(这里处理时直接找到根结点,在根节点处操作)。
还有在拓扑排序的实现上引用了队列进行模拟,起先处理时有记录每个点的入度个数,当入度为0时入队,如果出现过队列大小大于1的情况,说明排序不唯一,如果没有点入度为0 时,被确定排序的点不足n个时,为冲突。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define N 10005int n, m, cnt;
int X[2 * N], Y[2 * N], far[N], son[N];
char C[2 * N];
vector<int> G[N];int get(int x){return x != far[x]?far[x] = get(far[x]):x;
}
bool Union(int a, int b){if (a == b)return false;far[a] = b;return true;
}int main(){while (scanf("%d%d", &n, &m) != EOF){// Init.memset(son, 0, sizeof(son));for (int i = 0; i < n; ++i)G[far[i] = i].clear();cnt = n;// Read.for (int i = 0; i < m; i++){scanf("%d %c %d", &X[i], &C[i], &Y[i]);if (C[i] == '=' && Union(get(X[i]), get(Y[i])))cnt--;}// Handle.for (int i = 0; i < m; i++){int a = get(X[i]), b = get(Y[i]);if (C[i] == '<'){G[b].push_back(a);son[a]++;}else if (C[i] == '>'){G[a].push_back(b);son[b]++;}}queue<int> que;int ok = 0;for (int i = 0; i < n; i++)if (!son[i] && i == get(i))que.push(i);while (!que.empty()){if (que.size() > 1)ok = 1;int t = que.front();que.pop();cnt--;for (int i = 0; i < G[t].size(); i++)if (--son[G[t][i]] == 0)que.push(G[t][i]);}if (cnt > 0)printf("CONFLICT\n");else if (ok)printf("UNCERTAIN\n");elseprintf("OK\n");}return 0;}
这篇关于hud 1811 Rank of Tetris(拓扑排序+并查集+STL)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!