首页 > 代码库 > hdoj 1811 Rank of Tetris 【拓扑】+【并查集】

hdoj 1811 Rank of Tetris 【拓扑】+【并查集】

2024-08-03 00:01:31   218人阅读

Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5428    Accepted Submission(s): 1520


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"。
 

Input
本题目包含多组测试，请处理到文件结束。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系
 

Output
对于每组测试，在一行里按题目要求输出
 

Sample Input
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
 

Sample Output
OK
CONFLICT
UNCERTAIN

分析：因为是有相等的所以用并查集将相等的合成一个集合，之后再对处理过的图进行拓扑排序。

注：1》为什么用并查集将相等的合并到一起在排序就可以了，因为题目还有RP这一值，所以我们只需要对处理好的排序就好了，就是对父节点等于它本身的点来拓扑排序。

2》判断是冲突还是信息不完全，可以统计每一次入队列的的个数，如果是大于1的话，就说明有两个点的度数为0，那么他们的关系就无法确定，就是信息不完全，如果到最后还有没排好的就说明有冲突。。。

3》如果wa的话，试一下将判断‘>’改为‘<’，以及另外一个。

代码：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define M 10005
using namespace std;

vector<int>map[M];
int n, m, tot;
int fat[M], in[M], a[M<<1], b[M<<1];
char ch[M];

int f(int x){
	if(fat[x] != x) fat[x] = f(fat[x]);
	return fat[x];
}

int merge(int a, int b){
	int x = f(a); int y = f(b);
	if(x == y) return 0;
	if(x != y) fat[x] = y;
	return 1;
}

int toposort(){
	queue<int> q;
	int i, flag = 0;
	for(i = 0; i < n; i ++){
		if(in[i] == 0&&fat[i] == i) q.push(i);
	}
	
	while(!q.empty()){
		if(q.size() >= 2) flag = 1;
		int temp = q.front();
		q.pop();
		tot --;
		for(i = 0; i < map[temp].size(); i ++){
			if(! --in[map[temp][i]]){
				q.push(map[temp][i]);
			}
		}
	}
	if(tot > 0) flag = 2;
	return flag;
}

int main(){
	while(scanf("%d%d", &n, &m) == 2){
		memset(in, 0, sizeof(in));
		for(int i = 0; i < M; i ++){
			fat[i] = i;
			map[i].clear();
		}
		tot = n;
		for(int i = 0; i < m; i ++){
			scanf("%d %c %d", &a[i], &ch[i], &b[i]);
			if(ch[i] == '='&&merge(a[i], b[i])){
				tot --;
			}
		}
		for(int i = 0; i < m; i ++){
			int x = f(a[i]); int y = f(b[i]);
			//if(x == y) continue;
			if(ch[i] == '<'){  //就是这里，wa了好多次
				map[x].push_back(y);
				++in[y];
			}
			else if(ch[i] == '>'){
				map[y].push_back(x); ++in[x];
			}
		}
		int flag = toposort();
		if(flag == 2) printf("CONFLICT\n");
		else if(flag == 1) printf("UNCERTAIN\n");
		else printf("OK\n");
	}
	return 0;
}


hdoj 1811 Rank of Tetris 【拓扑】+【并查集】


联系
我们