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

轉載以下博客的文字：

鏈接入口：http://www.cnblogs.com/dongsheng/archive/2013/06/12/3133188.html

覺得這個博客寫的挺清晰，解釋的挺詳細的，自己多加思考就更清晰了。

大體思想：

1、如果兩個物種有聯系，不管是吃，被吃還是同類，它們之間應該是有一條徑路可達的，
也就是它們在一個合集中。
2、如果a,b有關系，b,c有關系，那么a,c之間的關系式可以通過兩者的關系推出來的。

OK，下面圍繞著上面的兩個思想來逐一拆分。
首先就是怎么把有關系的物種放到同一個合集中去,這就要需用到并查集了。每一次入輸d,x,y，
也就是相當于x,y之間有一條權為d的徑路。先忽略這個權值，直接斟酌路徑，那并查集的路徑建立就
不用我說了。一個parent數組,parent[i]表現從parent[i]到i有一條徑路。OK，那不同的物食圈就構
成了一個連通區域。每個連通區域都有一個根點節。

下面斟酌怎么處理這個權
先說點數學的貨色，任何一種偏序關系都足滿自反、對稱、傳遞。
自反：自己跟自己滿足偏序關系。
對稱：a,b的偏序關系為r，則b,a的偏序關系為~r.表現求反。
傳遞：a,b的偏序關系為r1，b,c的偏序關系為r2，a,c的偏序關系為r1+r2.

為了便利，用一個relation數組來維護這個權值。relation[i]表現的是i在所的連通區域的
根點節到i的關系。先略忽這個關系數組的維護過程，把團體的思緒理清晰。如果有兩個物種加進來，
就有兩種情況，要么它們在同一個連通集里頭。要么不在同一個連通集里頭。

一、兩者在同一個連通集里頭：
1、新加的關系表明x,y是同類，那么它們兩個分別到連通區域根點節的關系應該是一樣的，
要不就矛盾了。（記為case1）
2、如果新加的關系表明x,y不是同類，那么在當前參加y，x相對根節點的關系和x本來相對根點節的
關系應該是不變的，否則就矛盾了。（記為case2）

二、兩者在不同的連通集里頭：就直接連接兩個連通集就能夠了。（記為case3）

路徑壓縮處理：
由于后來物種會越來越多，我們不希望食物鏈拉的很長，所以會盡可能的讓全部的點節都直接和根節點
相連。這樣整個連通的圖就有點呈現出星形。

怎么維護關系數組：
數組里頭的每個元素的取值要么是0（同類），要么是1（父吃子），要么是2（子吃父）。至于為什么要
這么設置（因為題目中1表示同類，而我們定義0表示同類，相對都應該減一，所以題目中的2表示父吃子在我們這里
應該是2-1=1，,1表示父吃子），參考一另篇博客http://blog.csdn.net/c0de4fun/article/details/7318642，
這里是不能隨便定義的。設前面的數據我已經處理好了，現在要處理d,x,y.為了敘說的便利，
記relation[x]為x根->x.那么在現就有三種情況：
case1：（同一個集合且同類）
這種情況x根與y根雷同。如果x根->x與y根->y不同，表明x,y不是同類，與d=1矛盾。
case2：（同一個集合但不同類）
這種情況x根與y根雷同。如果參加y之后，（x根->x） = （x根（即y根）->y + y->x），如果新求出來
的關系與本身已有的x根->x的關系不同，則矛盾。
case3：（在不同集合中）
這種情況x根與y根不同。由于這里添加的是x到y的一條有向邊。將y根的父點節設置為x根，更新y根父點
節到x根的關系，即x根->y根=x根->x+x->y+y->y根，由于這里都是有向邊，所以更新關系的時候注意關
系的方向。這里需要注意，我們只更新了兩個根之間的關系，x根與原來的y所在的連通區域里頭的節點
的關系都沒有更新，這就是為什么要在一開始判斷之前就要調用Find函數，更新每個點節到其根點節的
關系。

初始條件：
有了這個遞推，就好辦了。初始條件parent就是并查集一般的初始條件，父點節于等自己。由于初始的
時候父節點是自己，當然自己跟自己的關系肯定是同類咯，也就是relation[i]=0

#include <iostream> #include<algorithm> #include<stdio.h> using namespace std; const int MAXN = 100010;int f[MAXN],rela[MAXN];int ff(int x) {int tem=f[x];if(tem!=x)f[x]=ff(tem),rela[x]=(rela[x]+rela[tem])%3;return f[x]; } int main() {int n,m,d,x,y;scanf("%d%d",&n,&m);for(int i=0;i<=MAXN;i++)f[i]=i,rela[i]=0;int s=0;while(m--){scanf("%d%d%d",&d,&x,&y);if(x > n || y > n){s++;continue;}if(d == 2 && x == y){s++;continue;}int tem1=ff(x),tem2=ff(y);if(tem1==tem2){if(d==1&&rela[x]!=rela[y])s++;else if(d==2&&rela[x]!=(rela[y] + 2)%3)s++;}else{f[tem2]=tem1;rela[tem2]=(rela[x]+(d-1)+(3-rela[y]))%3;}}printf("%d\n",s);return 0; }

轉載于:https://www.cnblogs.com/martinue/p/5490542.html

總結

以上是生活随笔為你收集整理的poj1182（加权值的并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

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