首页 > 代码库 > hdu 1811 Rank of Tetris - 拓扑排序 - 并查集
hdu 1811 Rank of Tetris - 拓扑排序 - 并查集
<style></style>
自从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"。
为了更好的符合那些爱好者的喜好，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 30 > 11 < 20 > 24 41 = 21 > 32 > 00 > 13 31 > 01 > 22 < 1
Sample Output
OKCONFLICTUNCERTAIN
用并查集将Rating相同的人缩成一个点。然后拓扑排序跑一发即可。
Code
1 /** 2 * hdu 3 * Problem#1811 4 * Accepted 5 * Time:93ms 6 * Memory:2064k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const double eps = 1e-6; 33 const int binary_limit = 128; 34 #define smin(a, b) a = min(a, b) 35 #define smax(a, b) a = max(a, b) 36 #define max3(a, b, c) max(a, max(b, c)) 37 #define min3(a, b, c) min(a, min(b, c)) 38 template<typename T> 39 inline boolean readInteger(T& u){ 40 char x; 41 int aFlag = 1; 42 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 43 if(x == -1) { 44 ungetc(x, stdin); 45 return false; 46 } 47 if(x == ‘-‘){ 48 x = getchar(); 49 aFlag = -1; 50 } 51 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 52 ungetc(x, stdin); 53 u *= aFlag; 54 return true; 55 } 56 57 ///map template starts 58 typedef class Edge{ 59 public: 60 int end; 61 int next; 62 Edge(const int end = 0, const int next = 0):end(end), next(next){} 63 }Edge; 64 65 typedef class MapManager{ 66 public: 67 int ce; 68 int *h; 69 Edge *edge; 70 MapManager(){} 71 MapManager(int points, int limit):ce(0){ 72 h = new int[(const int)(points + 1)]; 73 edge = new Edge[(const int)(limit + 1)]; 74 memset(h, 0, sizeof(int) * (points + 1)); 75 } 76 inline void addEdge(int from, int end){ 77 edge[++ce] = Edge(end, h[from]); 78 h[from] = ce; 79 } 80 inline void addDoubleEdge(int from, int end){ 81 addEdge(from, end); 82 addEdge(end, from); 83 } 84 Edge& operator [] (int pos) { 85 return edge[pos]; 86 } 87 inline void clear() { 88 delete[] edge; 89 delete[] h; 90 } 91 }MapManager; 92 #define m_begin(g, i) (g).h[(i)] 93 ///map template ends 94 95 typedef class union_found{ 96 public: 97 int *f; 98 union_found():f(NULL) {} 99 union_found(int points) {100 f = new int[(const int)(points + 1)];101 for(int i = 0; i <= points; i++)102 f[i] = i;103 }104 int find(int x) {105 if(f[x] != x) return f[x] = find(f[x]);106 return f[x];107 }108 void unit(int fa, int so) {109 int ffa = find(fa);110 int fso = find(so);111 f[fso] = ffa;112 }113 boolean connected(int a, int b) {114 return find(a) == find(b);115 }116 inline void clear() {117 delete[] f;118 }119 }union_found;120 121 typedef class Rank {122 public:123 int id;124 int dep;125 126 boolean operator < (Rank b) const {127 return dep < b.dep;128 }129 }Rank;130 131 int n, m;132 MapManager g;133 int* dag;134 Rank* rs;135 union_found uf;136 vector<Edge> rss;137 138 inline boolean init() {139 if(!readInteger(n)) return false;140 readInteger(m);141 g = MapManager(n, m);142 uf = union_found(n);143 dag = new int[(n + 1)];144 rs = new Rank[(n + 1)];145 memset(dag, 0, sizeof(int) * (n + 1));146 char opt;147 for(int i = 1, a, b; i <= m; i++) {148 readInteger(a);149 getchar();150 opt = getchar();151 readInteger(b);152 if(opt == ‘>‘)153 rss.push_back((Edge) {b, a});154 else if(opt == ‘<‘)155 rss.push_back((Edge) {a, b});156 else if(opt == ‘=‘)157 uf.unit(a, b);158 }159 for(int i = 0, a, b; i < (signed)rss.size(); i++) {160 a = uf.find(rss[i].end);161 b = uf.find(rss[i].next);162 g.addEdge(a, b);163 dag[b]++;164 }165 return true;166 }167 168 queue<int> que;169 inline void topu() {170 for(int i = 0; i < n; i++) {171 rs[i].id = i;172 rs[i].dep = 0;173 if(!dag[i] && uf.find(i) == i)174 que.push(i);175 }176 while(!que.empty()) {177 int e = que.front();178 que.pop();179 for(int i = m_begin(g, e); i; i = g[i].next) {180 int& eu = g[i].end;181 dag[eu]--;182 smax(rs[eu].dep, rs[e].dep + 1);183 if(!dag[eu])184 que.push(eu);185 }186 }187 }188 189 boolean* vis;190 inline void solve() {191 topu();192 for(int i = 0; i < n; i++)193 if(dag[i]) {194 puts("CONFLICT");195 return;196 }197 vis = new boolean[n + 1];198 memset(vis, false, sizeof(boolean) * (n + 1));199 for(int i = 0; i < n; i++) {200 if(uf.find(i) == i) {201 if(vis[rs[i].dep]) {202 puts("UNCERTAIN");203 return;204 }205 vis[rs[i].dep] = true;206 }207 }208 puts("OK");209 }210 211 inline void clear() {212 g.clear();213 uf.clear();214 rss.clear();215 delete[] dag;216 delete[] rs;217 }218 219 int main() {220 while(init()) {221 solve();222 clear();223 }224 return 0;225 }
hdu 1811 Rank of Tetris - 拓扑排序 - 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。