- 浏览: 316829 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://acm.hdu.edu.cn/showproblem.php?pid=1811
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则说明拓扑排序序列不唯一,用分叉树去理解的话,就是同一层有多个节点
*如果需要排序的总个数小于给定的个数,则说明存在回路
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则说明拓扑排序序列不唯一,用分叉树去理解的话,就是同一层有多个节点
*如果需要排序的总个数小于给定的个数,则说明存在回路
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> //#include <map> #include <queue> #include <utility> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; int pre[10005], L[20005], R[20005], ind[10005], n; //L:左值,R:右值 char ch[20005]; //ch: 中值,ind: 入度 struct node{ int son; //儿子的编号 node *next; //指向下一个儿子,即为son的兄弟 }*N[10005]; int find (int a) //并查集:寻找终极父节点,即a所属的集合的根节点 { while (a != pre[a]) a = pre[a]; return a; } void insert (int a, int b) //b插入作为a的儿子,a这个链表表示a的所有儿子,不包括孙子 { node *p = new node; p->son = b; p->next = N[a]; N[a] = p; } void init () //初始化 { int i; for (i = 0; i < n; i++) { pre[i] = i; ind[i] = 0; N[i] = NULL; } } int main() { int i, A, B, m, num; while (~scanf ("%d%d", &n, &m)) { init (); num = n; //num是需要排序的点的个数 for (i = 0; i < m; i++) { scanf ("%d %c %d", L+i, ch+i, R+i); if (ch[i] == '=') //=则合并为同一集合 { A = find (L[i]); B = find (R[i]); if (A != B) //需要排序的个数-1,既然相等就不需要进行拓扑了,顺序已定 pre[B] = A, num--; } } bool flag = false; for (i = 0; i < m; i++) //合并完之后才可以进行以下操作 { if (ch[i] == '=') //=的情况刚刚已经处理完 continue; A = find (L[i]); B = find (R[i]); if (A == B) {//两个值属于同一集合,也就是刚刚上面相等合并为同一集合,现在却不等了,矛盾! flag = true; break; //矛盾就可以直接退出循环了 } if (ch[i] == '>') { insert (A, B); //注意,必须用A,B(即集合的根节点)进行入边操作 ind[B]++; //入度+1 } else { insert (B, A); //同理 ind[A]++; } } if (flag) { puts ("CONFLICT"); //矛盾 continue; } queue<int> q; for (i = 0; i < n; i++) if (ind[i] == 0 && i == find(i)) q.push (i); //找到拓扑排序的终极父亲,入度为0,且为集合根节点 while (!q.empty()) { if (q.size() > 1)//(类似于分叉的树)同一层有多个点,则必有多个拓扑排序序列 flag = true; num--; //排好一个点了 int t = q.front(); q.pop(); for (node *i = N[t]; i; i = i->next) if (--ind[i->son] == 0)//入度为1才可入队列,为了防止重复入队列,自减 q.push (i->son); } if (num > 0) //根据题意,优先判断是否矛盾 puts ("CONFLICT"); else if (flag) //有多个拓扑排序序列,所以不确定 puts ("UNCERTAIN"); else puts ("OK"); } return 0; }
发表评论
-
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2688KIDx的解题报告 题 ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1436KIDx的解题报告 题目链接:http://acm ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1466KIDx的解题报告 题目链接:http://light ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 7101KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【完美匹配-KM算法】HDU总结
2011-10-02 14:35 7197KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2539http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1841KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1804http://acm.hdu.edu.cn/showprobl ... -
【并查集+贪心(或)最短路+二分枚举】HDU 1598
2011-08-27 23:25 4078http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2934首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1556KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2342http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1970http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2210http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1787http://acm.hdu.edu.cn/showprobl ... -
【次小生成树】POJ 1679 The Unique MST
2011-08-12 10:00 1042http://poj.org/problem?id=1679 ... -
【拓扑排序】HDU 2647 Reward【2012/3/25更新】
2011-08-11 19:26 1937http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序】HDU 1285 确定比赛名次
2011-08-10 21:38 1168http://acm.hdu.edu.cn/showprobl ... -
HDU_1856_More is better
2011-05-15 16:05 1062http://acm.hdu.edu.cn/showprobl ...
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
3. (HDUACM2010版_06)并查集(最小生成树).ppt:这是一个PPT文件,可能详细介绍了如何使用并查集来求解最小生成树的问题,包括理论知识、算法流程和示例解析。 4. hdoj1829二分图识别的并查集.txt:二分图是图论...
标题:“hdu排序练习”与描述“hdu ACM 各种排序”共同指向了HDOJ(Hangzhou Dianzi University Online Judge)平台上的排序算法练习。HDOJ是计算机科学与技术领域内,尤其是算法设计与分析方向,非常受欢迎的一个...
3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
【并查集详解】 并查集(Disjoint Set)是一种数据结构,用于高效处理不相交集合的合并和查询操作。在算法竞赛中,它常用于解决如连通子图、最小生成树(如Kruskal算法)以及最近公共祖先(LCA)等问题。其核心思想...
本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...
3. **图论**:包括最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)、最小生成树(Prim、Kruskal)、拓扑排序等。 4. **字符串处理**:如KMP算法、Manacher's Algorithm、后缀数组、Z-Algorithm等,常用于...
HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...
7. **排序与搜索**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法,以及线性搜索、二分搜索等查找算法。 8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。 6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等...
1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小生成树、拓扑排序等)和动态规划等。 2. **数据结构**:如链表、...
6. **数据结构**:线段树、斐波那契堆、平衡树(AVL、红黑树)、字典树(Trie)、并查集等,这些高级数据结构可以高效地解决区间查询、维护、集合操作等问题。 7. **几何算法**:二维和三维几何问题,如点线面的...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...