題目：http://poj.org/problem?id=2912

?

題意：n個人進(jìn)行m輪剪刀石頭布游戲(0<n<=500,0<=m<=2000)，接下來m行形如x, y, ch的輸入，ch='='表示x, y平局，ch='>'表示x贏y，ch='<'表示x輸y, 但是我們不知道x, y的手勢是什么; 其中有一個人是裁判，它可以出任意手勢，其余人手勢相同的分一組，共分為三組，可以存在空組，也就是說除了裁判外，其余人每一次出的手勢都相同，問能不能確定裁判是幾號，如果能，輸出最少在第幾輪可以確定；

?

思路：感覺此題的題意有點模糊，加上樣例才勉強看懂；如果能唯一確定裁判的編號，按照格式輸出編號和能確定裁判的最少輪數(shù)，如果存在一個裁判但不能確定的話輸出Can not determine，如果由輸入得到有多個裁判或者一個裁判都沒有，那么輸出Impossible; 如果順著題目的思路去想的話，因為裁判手勢可以是任意的，很難確定編號之間的相對關(guān)系；又因為除了裁判外其余人的手勢是不變的，那么我們一定可以將除裁判外的人分成三組(可以有空組)；想到這里我們可以發(fā)現(xiàn)，如果我們假設(shè)某個編號為裁判，如果除了它外其余人的關(guān)系沒有矛盾，那么它就可能是裁判；此題的數(shù)據(jù)不大, 那么只要我們枚舉每一個節(jié)點，假設(shè)其為裁判，如果我們得到的可能為裁判的節(jié)點唯一，那么它就是裁判，如果得到可能為裁判的節(jié)點有多個，那么就不能確定裁判，如果可能為裁判的節(jié)點一個都沒有，就是Impassible啦～

現(xiàn)在我們已經(jīng)確定的了三種情況，剩下能確定裁判的時候還要輸出最少幾行能確定，我們是通過排除法來確定裁判編號的，枚舉每個編號為裁判，一但在某一行輸入中出現(xiàn)矛盾，我們就確定它不是裁判，那么n-1個出現(xiàn)矛盾的枚舉中出現(xiàn)矛盾最晚的那個行數(shù)即為我們能確定裁判所需的最少行數(shù)啦(因為我們要排除n-1個編號才能確定裁判的編號嘛)～

?

代碼：

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define MAXN 510 5 using namespace std; 6 7 int rank[MAXN], pre[MAXN]; //***rank數(shù)組存儲當(dāng)前節(jié)點與父親節(jié)點的關(guān)系!注意不是與根節(jié)點的關(guān)系!!! 8 9 int find(int x){//**遞歸路徑壓縮 10 if(pre[x]!=x){ 11 int px=find(pre[x]); 12 rank[x]=(rank[x]+rank[pre[x]])%3; //***回溯時改變rank[x]的值,這個公式我們可以由枚舉得出 13 pre[x]=px; //***將 x 的父親節(jié)點變?yōu)楦?jié)點,即 x 節(jié)點直接指向根節(jié)點 14 } 15 return pre[x]; 16 } 17 18 int jion(int x, int y, int d){ 19 int px=find(x); 20 int py=find(y); 21 if(px==py){ //***若 x, y 都已經(jīng)加入并查集,即相對關(guān)系已經(jīng)確定,遞歸壓縮路徑后 x, y 的根節(jié)點即為他們的父節(jié)點, 我們可以由rank得到 x, y的關(guān)系,因為我們加入并查集的 x, y的關(guān)系都是真確的,所以如果d值與我們由rank得到的關(guān)系不同,那么其為假話 22 if((rank[y]-rank[x]+3)%3!=d){ //***x, y的關(guān)系我們可以由枚舉得出 23 return 1; 24 } 25 }else{ 26 pre[py]=px; 27 rank[py]=(rank[x]-rank[y]+d+3)%3; //***得到合并后px與py的關(guān)系,此處的公式也是可以通過枚舉得出的 28 } 29 return 0; 30 } 31 32 int main(void){ 33 int n, m; 34 while(~scanf("%d%d", &n, &m)){ 35 int x[MAXN*4], y[MAXN*4], d; 36 char ch[MAXN*4]; 37 for(int i=1; i<=m; i++){ 38 scanf("%d%c%d", &x[i], &ch[i], &y[i]); 39 } 40 int tot=0, flag=1, gg=0, jj=0; //***tot統(tǒng)計裁判個數(shù) 41 for(int i=0; i<n; i++){ //***枚舉，假設(shè)i為裁判，若無矛盾即可行 42 flag=1; 43 for(int j=0; j<n; j++){ //**初始化 44 rank[j]=0; 45 pre[j]=j; 46 } 47 for(int j=1; j<=m; j++){ //**建立關(guān)系并查集 48 if(x[j]==i||y[j]==i){ //***裁判可以任意出手勢，把裁判放在并查集外面 49 continue; 50 } 51 if(ch[j]=='='){ 52 d=0; 53 }else if(ch[j]=='>'){ 54 d=1; 55 }else{ 56 d=2; 57 } 58 if(jion(x[j], y[j], d)){ //**判斷是否有矛盾 59 gg=max(j, gg); //**維護出現(xiàn)矛盾最大行數(shù) 60 flag=0; 61 break; 62 } 63 } 64 if(flag){ //**沒出現(xiàn)矛盾，即當(dāng)前節(jié)點可以是裁判 65 tot++; 66 jj=i; //**記錄裁判節(jié)點號 67 } 68 } 69 if(!tot){ 70 printf("Impossible\n"); 71 }else if(tot>1){ 72 printf("Can not determine\n"); 73 }else{ 74 printf("Player %d can be determined to be the judge after %d lines\n", jj, gg); 75 } 76 } 77 return 0; 78 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/geloutingyu/p/6145706.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的poj2912(种类并查集+枚举)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。