多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內(nèi)最全IT社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當前位置:首頁 > php開源 > php教程 > HDU1811Rank of Tetris(并查集+拓撲排序)

HDU1811Rank of Tetris(并查集+拓撲排序)

來源:程序員人生   發(fā)布時間:2015-03-09 08:36:22 閱讀次數(shù):2845次

Rank of Tetris

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


Problem Description
自從Lele開發(fā)了Rating系統(tǒng),他的Tetris事業(yè)更是如虎添翼,不久他遍把這個游戲推向了全球。

為了更好的符合那些愛好者的喜好,Lele又想了1個新點子:他將制作1個全球Tetris高手排行榜,定時更新,花樣要比福布斯富豪榜還響。關于如何排名,這個不用說都知道是根據(jù)Rating從高到低來排,如果兩個人具有相同的Rating,那就按這幾個人的RP從高到低來排。

終究,Lele要開始行動了,對N個人進行排名。為了方便起見,每一個人都已被編號,分別從0到N⑴,并且編號越大,RP就越高。
同時Lele從狗仔隊里獲得1些(M個)關于Rating的信息。這些信息可能有3種情況,分別是"A > B","A = B","A < B",分別表示A的Rating高于B,等于B,小于B。

現(xiàn)在Lele其實不是讓你來幫他制作這個高手榜,他只是想知道,根據(jù)這些信息是不是能夠肯定出這個高手榜,是的話就輸出"OK"。否則就請你判斷出錯的緣由,究竟是由于信息不完全(輸出"UNCERTAIN"),還是由于這些信息中包括沖突(輸出"CONFLICT")。
注意,如果信息中同時包括沖突且信息不完全,就輸出"CONFLICT"。
 

Input
本題目包括多組測試,請?zhí)幚淼轿募Y束。
每組測試第1行包括兩個整數(shù)N,M(0<=N<=10000,0<=M<=20000),分別表示要排名的人數(shù)和得到的關系數(shù)。
接下來有M行,分別表示這些關系
 

Output
對每組測試,在1行里按題目要求輸出
 

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
 

Author
linle
 解題:并查集:用于無向的,所以只能用在等號上,而等號就說明相等的點是等價的,可以用1個點來代替相等點的集合。也就是縮點。
拓撲:1個個點去掉,如果同時可以去掉2個點或以上的點,則說明信息不全。如果還有點不能去掉,則說明是有環(huán),有沖突。
#include<iostream> #include<vector> #include<stdio.h> #include<string.h> using namespace std; const int N = 10005; int indu[N],n,fath[N],idk; vector<int>map[N]; void init() { for(int i=0;i<=n;i++) { indu[i]=0,fath[i]=i; map[i].clear(); } idk=0; } int findfath(int x) { if(x==fath[x]) return fath[x]; fath[x]=findfath(fath[x]); return fath[x]; } void setfath(int x,int y) { x=findfath(x); y=findfath(y); fath[x]=y; } void topu() { int k=0,s[N],uncertain=0,node; for(int i=0;i<n;i++) { if(fath[i]==i) idk++; if(indu[i]==0&&fath[i]==i)//fath[i]==i是用于判斷非等號關第的點,除終究父節(jié)點,可以看做是等號點的集合 s[k++]=i; } while(k--) { if(k>0) uncertain=1; idk--; node=s[k]; for(int i=0;i<map[node].size();i++) { int t=map[node][i]; indu[t]--; if(indu[t]==0) s[k++]=t; } } if(idk>0) printf("CONFLICT "); else if(uncertain) printf("UNCERTAIN "); else printf("OK "); } int main() { int a[N],b[N],m; char f[N]; while(scanf("%d%d",&n,&m)>0) { init(); for(int i=0;i<m;i++) { scanf("%d %c %d",&a[i],&f[i],&b[i]); if(f[i]=='=') setfath(a[i],b[i]); } for(int i=0;i<m;i++) if(f[i]!='=') { a[i]=findfath(a[i]); b[i]=findfath(b[i]); if(f[i]=='>') { indu[b[i]]++; map[a[i]].push_back(b[i]); } else { indu[a[i]]++; map[b[i]].push_back(a[i]); } } topu(); } }


生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 欧美xxxx成人免费网站 | 午夜爽爽爽男女免费观看hd | 亚洲 欧美 中文 日韩欧美 | 国产在线精品一区二区三区 | 欧美最猛黑人xxxx黑人 | 成年人视频免费网站 | 日韩大片免费在线观看 | 亚洲乱码在线 | 性爱视频在线播放 | 国产精品视频一区二区三区w | freexxxhd性欧美 | 亚洲成人在线免费 | 波多野结中文字幕在线69视频 | 亚洲成av人片在线观看 | 亚洲激情另类 | 亚洲国产情侣一区二区三区 | 国产美女无遮挡免费视频网站 | 亚洲欧美日韩国产综合高清 | 亚洲二区在线观看 | 99久久伊人| 夜夜网站| 亚洲视频播放 | 另类亚洲图片 | 亚洲人成在线影院 | 欧美freesex黑人又粗又 | www久久爱| 一级欧美一级日韩 | 激情影院在线视频永久观看 | 亚洲视频在线观看地址 | 欧美free hd xxxx movies| 国产一区二区日韩欧美在线 | 国产精品成人免费综合 | 456在线视频 | 国产成人综合久久 | 色网站在线 | 日韩一区二区三区四区区区 | 毛片毛片毛片 | 成人午夜网站 | 午夜精品久久久久久 | 久久久久久久99精品免费 | 一级做a爱久久久久久久 |