hud 1811 Rank of Tetris(拓扑排序+并查集+STL)

2024-06-05 05:32

本文主要是介绍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


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

一道很好的拓扑排序题,因为有等号的缘故,所以加大了难度。

题目数据量比较大,肯定不能用邻接矩阵来储存关系,会超内存,所以果断选择用领接表,然后用了一下午的时间学习了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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032196

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i

POJ1703带权并查集

D: u v  u与v在不同的集合 A: u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验