Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 64875 Accepted: 19085
Description

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。
現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。
有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：
第一種說法是”1 X Y”，表示X和Y是同類。
第二種說法是”2 X Y”，表示X吃Y。
此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。
1） 當前的話與前面的某些真的話沖突，就是假話；
2） 當前的話中X或Y比N大，就是假話；
3） 當前的話表示X吃X，就是假話。
你的任務是根據給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數。
Input

第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。
Output

只有一個整數，表示假話的數目。
Sample Input

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
Sample Output

3
Source

【題解】

哎。網上有牛人寫了很完整的題解。
我復制一下。

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 - 路徑壓縮，以及節點間關系確定 確定了權值之后，我們要確定有關的操作。 我們把所有的動物全初始化。 struct Animal { int num; //該節點（node）的編號 int parent; //該node的父親 int relation; //該node與父節點的關系，0同類，1被父節點吃，2吃父節點 }; Animal ani[50010]; 初始化為 For i = 0 to N do ani[i].num = i; ani[i].parent = i; ani[i].relation = 0 ; //自己和自己是同類 End For (1)路徑壓縮時的節點算法 我們設A,B,C動物集合如下：（為了以后便于舉例） A = { 1 , 2 , 3 ,4 ,5 } B = { 6 , 7 , 8 ,9 ,10} C = { 11, 12, 13,14,15} 假如我們已經有了一個集合，分別有3個元素 SET1 = {1,2}，我們規定集合中第一個元素為并查集的“代表” 假如現在有語句： 2 2 6 這是一句真話 2是6的父親 ani[6].parent = 2; ani[6].relation = 1; 那么，6和1的關系如何呢？ ani[2].parent = 1; ani[2].relation = 0; 我們可以發現6與2的關系是 1. 通過窮舉我們可以發現 ani[now].parent = ani[ani[now].parent].parent; ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 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 這就是路徑壓縮的節點算法 (2) 集合間關系的確定 在初始化的時候，我們看到，每個集合都是一個元素，就是他本身。 這時候，每個集合都是自洽的（集合中每個元素都不違反題目的規定） 注意，我們使用并查集的目的就是盡量的把路徑壓縮，使之高度盡量矮 假設我們已經有一個集合 set1 = {1,2,7,10} set2 = {11,4,8,13},每個編號所屬的物種見上文 set3 = {12,5,4,9} 現在有一句話 2 13 2 這是一句真話,X = 13,Y = 2 我們要把這兩個集合合并成一個集合。 直接 int a = findParent(ani[X]); int b = findParent(ani[Y]); ani[b].parent = a; 就是把Y所在集合的根節點的父親設置成X所在集合的根節點。 但是，但是！！！！ Y所在集合的根結點與X所在集合的根節點的關系！！！要怎么確定呢？ 我們設X,Y集合都是路徑壓縮過的，高度只有2層 我們先給出計算的公式 ani[b].relation = ( 3 - ani[Y].relation + ( d - 1 ) + ani[X].relation) % 3; 這個公式，是分三部分，這么推出來的 第一部分，好理解的一部分： ( d - 1 ) :這是X和Y之間的relation，X是Y的父節點時，Y的relation就是這個 3 - ani[Y].relation = 根據Y與根節點的關系，逆推根節點與Y的關系 這部分也是窮舉法推出來的，我們舉例： j 子 父相對于子的relation（即假如子是父的父節點，那么父的relation應該是什么，因為父現在是根節點，所以父.relation = 0，我們只能根據父的子節點反推子跟父節點的關系） 0 ( 3 - 0 ) % 3 = 0 1（父吃子） ( 3 - 1 ) % 3 = 2 //父吃子 2（子吃父) ( 3 - 2 ) % 3 = 1 //子吃父，一樣的哦親 —————————————————————————————————————————————————————— 我們的過程是這樣的： 把ani[Y]，先連接到ani[X]上，再把ani[Y]的根節點移動到ani[X]上，最后，把ani[Y]的根節點移動到ani[X]的根節點上，這樣算relation的 還記得么，如果我們有一個集合，壓縮路徑的時候父子關系是這么確定的 ani[爺爺].relation = ( ani[父親].relation + ani[兒子].relation ) % 3 我們已知道,( d - 1 )就是X與Y的relation了 而 (3 - ani[Y].relation)就是 以Y為根節點時，他的父親的relation 那么 我們假設把Y接到X上，也就說，現在X是Y的父親，Y原來的根節點現在是Y的兒子 Y的relation + ani[Y]根節點相對于ani[Y]的relation ( ( d - 1 ) + ( 3 - ani[Y].relation) ) % 3 就是ani[Y]的父親節點與ani[X]的relation了！ 那么，不難得到，ani[Y]的根節點與ani[X]根節點的關系是： ( ( d - 1 ) + ( 3 - ani[Y].relation) + ani[X].relation ) % 3 ->應用了同余定理 注意，這個當所有集合都是初始化狀態的時候也適用哦 還是以最開頭我們給的三個集合（分別代表三個物種）為例 2 1 6 帶入公式 ani[6].relation = ( ( 2 - 1 ) + ( 3 - 0 ) + 0 ) % 3 = 1 也就是，6被1吃 Part III - 算法正確性的證明 首先，兩個自洽的集合，合并以后仍然是自洽的 這個不難想吧，數學上有個什么對稱性定理跟他很像的。 如果理解不了，就這么想！！ 當set1和set2合并之后，set2的根節點得到了自己關于set1根節點的 正確relation值，變成了set1根節點的兒子，那么 set2的所有兒子只要用 ( ani[X].relation + ani[Y].relation ) % 3就能得到自己正確的relation值了 所以說，針對不在同一集合的兩個元素的話，除非違背了（2）和（3），否則永遠是真的 （無論這句話說的是什么，我們都可以根據所給X,Y推出兩個子節點之間應有的關系，這個關系一確定，所有兒子的關系都可以確定） 其實所有的不同集合到最后都會被合并成一個集合的。 我們只要在一個集合中找那些假話就可以了。 首先，如何判斷 1 X Y是不是假話。//此時 d = 1 if ( X 和 Y 不在同一集合) Union(x,y,xroot,yroot,d) else if x.relation != y.relation ->假話 其次，如何判斷 2 X Y是不是假話 //此時d = 2 if ( X 和 Y 不在同一集合） Union(x,y,xroot,yroot,d) else (ani[y].relation + 3 - ani[x].relation ) % 3 != 1 ->假話 這個公式是這么來的： 3 - ani[x].relation得到了根節點關于x的relation ani[y] + 3 - ani[x].relation得到了y關于x的relation 所以，只要y關于x的relation不是1，就是y不被x吃的話，這句話肯定是假話！ (2)路徑壓縮要特別注意的一點（錯在這里，要檢討自己） 路徑壓縮的時候，記得要 先findParent，再給當前節點的relation賦值。 否則有可能因為當前節點的父節點的relation不正確而導致錯的稀里嘩啦。 例子： set1 = {1,2,7,10} set2 = {3,4,8,11} set3 = {12,5,14,9} Union(1,3,1,3,1) Union(3,12,3,12,2) 1 5 1 算5的relation 如果不先更新parent的relation，算出來應該是 ( 3 - 0 + 0 + 1 ) % 3 = 1，5被1吃，顯然不對 這里面，+ 0的那個0是指根節點 12 的relation（未更新，這里的0是指12與11的relation） 如果更新完了的話，應該是 ( 3 - 0 + 2 + 1 ) % 3 = 0 ,5與1是同一物種，對了 這里面的 2 是更新節點12的relation（12與1的relation）

那里把Y接在X的根節點的下方本來應該是這樣的。

但是我們可以換個思路
變成如下的放法。

把那三個用紅下劃線標記的東西累加起來就是relation(a,b)了
知道relation(a,b)了。
令fa[b] = a;
然后再變回

知道了relation(a,b),我們可以通過lelation(a,b)在路徑壓縮的時候獲取relation(b,y);
然后是判斷是否為假話的問題。
我們需要判斷任意兩個點(a,b)的關系;
因為最后進行完路徑壓縮每個并查集都只有兩層。
要獲取relation(a,b);
就查看(relation[a]+3-relation[b])%3;
為0表示相同物種，1表示b吃a,2表示a吃b;
這樣理解(高度只有兩層)

#include <cstdio>const int MAXN = 59999;struct node {int fa, relation; };int n, k,d,x,y,fade = 0; node ani[MAXN];int findfather(int x) {if (ani[x].fa == x)return x;int olfa = ani[x].fa;ani[x].fa = findfather(ani[x].fa);ani[x].relation = (ani[x].relation + ani[olfa].relation) % 3;return ani[x].fa; }int main() {//freopen("F:\\rush.txt", "r", stdin);scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++){ani[i].fa = i;ani[i].relation = 0;}for (int i = 1; i <= k; i++){scanf("%d%d%d", &d, &x, &y);if ((x > n || y > n) || (d == 2 && x==y)){fade++;continue;}int a = findfather(x);int b = findfather(y);if (a != b){ani[b].fa = a;ani[b].relation = (3 - ani[y].relation + d - 1 + ani[x].relation) % 3;}else{int temp = (ani[y].relation + 3 - ani[x].relation) % 3;if (d == 1){if (temp != 0)fade++;}elseif (d == 2){if (temp != 1)fade++;}}}printf("%d\n", fade);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7632184.html

總結

以上是生活随笔為你收集整理的【29.42%】【POJ 1182】食物链的全部內容，希望文章能夠幫你解決所遇到的問題。

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