動物王國中有三類動物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
其實大一暑假講并查集的時候就做過這道題，但是當時不太理解，而且之后并查集的題目做的很少。就沒再做。。
三種生物有可能會形成一個環，A吃B，B吃C,C吃A。
假如先出現的前兩條，我們則認定是正確的（因為目前的條件判斷不出是否錯誤）。但是加上第三條之后，我們怎么判斷是否正確呢？三個生物之間的關系形成了一個環，那么他們之間的關系可以通過取模來確定。假如A與B之間是同類，那么他們之間的聯系就是0，如果A吃B，那么他們之間的聯系就是1，如果A吃B的父親也吃B，那么A與B的父親之間的聯系就是2。

路徑壓縮之后：
代碼如下：
poj的代碼單組讀入必須是單組讀入，多組讀入會wa。。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<string> using namespace std;const int maxx=5e4+100; int f[maxx],dis[maxx]; int n,m;inline int getf(int u) {int x;if(u!=f[u]){x=getf(f[u]);dis[u]=(dis[u]+dis[f[u]])%3;f[u]=x;}return f[u]; } inline int merge(int u,int v,int val) {int t1=getf(u);int t2=getf(v);if(t1==t2){if((dis[v]-dis[u]+3)%3!=val) return 1;else return 0;}else{f[t2]=t1;dis[t2]=(dis[u]-dis[v]+3+val)%3;return 0;} } int main() {int x,y,op;scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) dis[i]=0,f[i]=i;int ans=0;while(m--){scanf("%d%d%d",&op,&x,&y);if(x>n||y>n) ans++;else if(op==2&&x==y) ans++;else if(merge(x,y,op-1)) ans++;}printf("%d\n",ans);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的食物链 POJ - 1182（带权并查集模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

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