題意

　　有三類動物A,B,C，題中給出兩種關系：

　　　　1 x y :x y 同類

　　　　2 x y :x吃y

　　對于假話的定義：

　　　　1.當前的話與前面的某些真的話沖突，就是假話；

　　　　2.當前的話中X或Y比N大，就是假話；

　　　　3.當前的話表示X吃X，就是假話。

　　現在給出n句這樣的關系，求假話個數。

分析

　　這是第二次寫這道題了，第一次是去年剛學并查集的時候。當初囫圇吞棗A了，現在拿出來發現自己根本就沒明白。

　　感覺，經典的題還是要時常拿出來做一做。

　　剛才某人吐槽：這題比就我小4歲。呵呵....

?

　　廢話少說，說正題。

?

　　看題解寫的，這個人的分析很詳細哦~！膜拜！http://blog.csdn.net/c0de4fun/article/details/7318642

　　感覺他說的太詳細了，所以鄙人就摘抄并整理修改一下這位大神的，自己也沒什么可寫的了...謝謝大神

　　Part I - 權值(relation)的確定。
　　　　我們根據題意，森林中有3種動物。A吃B，B吃C，C吃A。
　　　　我們還要使用并查集，那么，我們就以動物之間的關系來作為并查集每個節點的權值。
　　　　注意，我們不知道所給的動物（題目說了，輸入只給編號）所屬的種類。

　　　　所以，我們可以用動物之間“相對”的關系來確定一個并查集。
　　　　　　　　0 - 這個節點與它的父節點是同類
　　　　　　　　1 - 這個節點被它的父節點吃
　　　　　　　　2 - 這個節點吃它的父節點。

　　　　注意，這個0,1,2所代表的意義不是隨便制定的，我們看題目中的要求。
　　　　說話的時候，第一個數字（下文中，設為d）指定了后面兩種動物的關系：
　　　　　　　　1 - X與Y同類
　　　　　　　　2 - X吃Y

　　　　我們注意到，當 d = 1的時候，( d - 1 ) = 0，也就是我們制定的意義
　　　　當 d = 2的時候，( d - 1 ) = 1，代表Y被X吃，也是我們指定的意義。
　　　　所以，這個0,1,2不是隨便選的

　　Part II - 路徑壓縮，以及節點間關系確定
　　　　確定了權值之后，我們要確定有關的操作。
　　　　我們把所有的動物全初始化 relation[i]=0,f[i]=i

　　　　(1)路徑壓縮時的節點算法

　　　　通過窮舉我們可以發現

　　　　　　f[now]=f[f[now]]

　　　　　　relation[now]=(relation[now]+relation[f[now]]) % 3

　　　　這個路徑壓縮算法是正確的
　　　　關于這個路徑壓縮算法，還有一點需要注意的地方，我們一會再談
　　　　注意，根據當前節點的relation和當前節點父節點的relation推出
　　　　當前節點與其父節點的父節點的relation這個公式十分重要！！
　　　　它推不出來下面都理解不了！！自己用窮舉法推一下：
　　　　好吧，為了方便伸手黨，我給出窮舉過程
　　　　　　　　 ? ? ? ?i ? ? ?j
　　　　　　　 爺爺 ?父親 兒子 ? ? ?兒子與爺爺
　　　　　　　　　　?0 ? ? ?0 ? ? ?(i + j)%3 = 0
　　　　　　　　　　?0 ? ? ?1 ? ? ?(i + j)%3 = 1
　　　　　　　　　　?0 ? ? ?2 ? ? ?(i + j)%3 = 2
　　　　　　　　　　?1 ? ? ?0 ? ? ?(i + j)%3 = 1
　　　　　　　　　　?1 ? ? ?1 ? ? ?(i + j)%3 = 2
　　　　　　　　　　?1 ? ? ?2 ? ? ?(i + j)%3 = 0
　　　　　　　　　　?2 ? ? ?0 ? ? ?(i + j)%3 = 2
　　　　　　　　　　?2 ? ? ?1 ? ? ?(i + j)%3 = 0
　　　　　　　　　　?2 ? ? ?2 ? ? ?(i + j)%3 = 1
　　　　嗯，這樣可以看到，( 兒子relation + 父親relation ) % 3 = 兒子對爺爺的relation

　　　　　　所以有relation[now]=(relation[now]+relation[f[now]]) % 3
　　　　　　這就是路徑壓縮的節點算法

　　　　(2) 集合間關系的確定
　　　　　　　　relation[find(y)]=(3-relation[y]+(d-1)+relation[x]) % 3;
　　　　　　　　這個公式，是分三部分，這么推出來的：
　　　　　　　　( d - 1 ) :這是X和Y之間的relation，X是Y的父節點時，Y的relation就是這個
　　　　　　　　3 - relation[y] = 根據Y與根節點的關系，逆推根節點與Y的關系
　　　　　　　　　　　　這部分也是窮舉法推出來的，我們舉例：
　　　　　　　　　　　　　　0（父子同類）( 3 - 0 ) % 3 = 0
　　　　　　　　　　　　　　1（父吃子） ( 3 - 1 ) % 3 = 2 //父吃子
　　　　　　　　　　　　　　2（子吃父) ( 3 - 2 ) % 3 = 1 //子吃父，一樣的哦親

　　　　　　　　所以有y的父結點與x的父結點關系relation[find(y)]=(3-relation[y]+(d-1)+relation[x]) % 3;
　　　　　　　　注意，這個當所有集合都是初始化狀態的時候也適用

　　Part III - 判斷

　　　　先處理特殊情況：　　　　　　

　　　　1.當x>n或y>n時，為假話（在這里竟然wa了一次...囧還是太不認真了）

　　　　 2.當d=2而x=y時，為假話

　
　　　　其實所有的不同集合到最后都會被合并成一個集合的。我們只要在一個集合中找那些假話就可以了。

　　　　　　(1)首先，如何判斷
　　　　　　　　1 X Y是不是假話。//此時 d = 1
　　　　　　　　if ( X 和 Y 不在同一集合)?Union(x,y,xroot,yroot,d)?　　

　　　　　　　　　　　　　　　　　　　　else?if x.relation != y.relation ->假話

　　　　　　(2)其次，如何判斷
　　　　　　　　2 X Y是不是假話 //此時d = 2
　　　　　　　　if ( X 和 Y 不在同一集合）Union(x,y,xroot,yroot,d)
　　　　　　　　　　　　　　　　　　　　else?(relation [y]+ 3 - relation[x] ) % 3 != 1 ->假話
　　　　　　　　這個公式是這么來的：
　　　　　　　　　　3 - relation[x]得到了根節點關于x的relation，
　　　　　　　　　　relation [y]+ 3 - relation[x]得到了y關于x的relation
　　　　　　　　　　所以，只要y關于x的relation不是1，就是y不被x吃的話，這句話肯定是假話！

?

　　　　　　綜合(1) 和(2),無論d=1或2，只要滿足?((relation[y]-relation[x]+3) Mod 3)<>(d-1)?即為假話

Accepted Code

1 { 2 PROBLEM:poj1182 noi2001 食物鏈 3 AUTHER:Rinyo 4 MEMO:并查集 5 } 6 7 Program poj1182; 8 Const 9 Infile = 'poj1182.in'; 10 Outfile = 'poj1182.out'; 11 Var 12 relation,f:Array[0..50030]Of Longint; 13 n,k,d,x,y,ans,i,fx,fy:Longint; 14 Function find(x:Longint):Longint; 15 Var 16 fx:Longint; 17 Begin 18 If f[x]=x Then Exit(x) 19 Else Begin 20 fx:=find(f[x]); 21 relation[x]:=(relation[x]+relation[f[x]]) Mod 3; 22 f[x]:=fx; 23 Exit(fx); 24 End; 25 End; 26 Procedure union(x,y,fx,fy,d:Longint); 27 Begin 28 f[fy]:=fx; 29 relation[fy]:=(3-relation[y]+d-1+relation[x]) Mod 3; 30 End; 31 Begin 32 Assign(input,infile);Reset(input); 33 Assign(output,outfile);Rewrite(output); 34 ReadLn(n,k); 35 For i:=1 To n Do Begin 36 f[i]:=i; 37 relation[i]:=0; 38 End; 39 For i:=1 To k Do Begin 40 ReadLn(d,x,y); 41 If (x>n) or (y>n) Then Begin 42 Inc(ans); 43 Continue; 44 End; 45 If (d=2) And (x=y) Then Begin 46 Inc(ans); 47 Continue; 48 End; 49 fx:=find(x);fy:=find(y); 50 If fx<>fy Then union(x,y,fx,fy,d); 51 Else Begin 52 If (((relation[y]-relation[x]+3) Mod 3)<>(d-1)) Then Inc(ans) 53 End; 54 End; 55 WriteLn(ans); 56 Close(input);Close(output) 57 End. 58

總結

以上是生活随笔為你收集整理的并查集/poj1182 noi2001食物链eat的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。