今天寫了道并查集的題，看來并查集的題刷少了，，，，，用法好神奇啊！！！開三倍并查集

用i表示自己，i+n存天敵，i+2*n存可以克制de，再邏輯判斷一下即可。

所以，要意識到并查集的分類處理可以開不同倍數的空間來適應題目要求。

?

1074 食物鏈

?

2001年NOI全國競賽

?時間限制: 3 s ?空間限制: 64000 KB ?題目等級 : 鉆石 Diamond 題解 題目描述?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 Description

第一行是兩個整數N和K，以一個空格分隔。 　　

以下K行每行是三個正整數D，X，Y，兩數之間用一個空格隔開，其中 D 表示說法的種類。 　　

若D=1，則表示X和Y是同類。 　　

若D=2，則表示X吃Y。

輸出描述?Output Description

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

樣例輸入?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

數據范圍及提示?Data Size & Hint

輸入文件??

?對7句話的分析 100 7

1 101 1　　假話

2 1 2　　? 真話

2 2 3　　? 真話

2 3 3　　? 假話

1 1 3　　? 假話

2 3 1　　? 真話

?1 5 5　　? 真話

#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #define fr(i,l,r) for(int i=l;i<=r;++i)//懶。。。。。。。 using namespace std; int n,m,D,x,y,ans; int f[200000]; int find(int a){if(f[a]!=a)f[a]=find(f[a]);return f[a];} void make(int x1,int y1){if(find(x1)!=find(y1))f[find(x1)]=find(y1);} int main(){scanf("%d%d",&n,&m);fr(i,1,3*n)f[i]=i;fr(i,1,m){scanf("%d%d%d",&D,&x,&y);if((x>n)||(y>n)||(x==y&&D==2)){ans++;continue;}if(D==1){if(find(x)==find(2*n+y)||find(n+x)==find(y)||find(x)==find(n+y)||find(2*n+x)==find(y)/*吃他的他吃的不能搞 */){ans++;continue;}make(x,y),make(x+n,y+n),make(x+2*n,y+2*n);}if(D==2){//x搞yif(find(y)==find(x)||find(y+n)==find(x)||find(y)==find(x+2*n)){ans++;continue;}make(x+2*n,y+n),make(x+n,y),make(x,y+2*n);}}printf("%d",ans);return 0; }

?

轉載于:https://www.cnblogs.com/zzmmm/p/6501182.html

總結

以上是生活随笔為你收集整理的NOI[2001]食物链的全部內容，希望文章能夠幫你解決所遇到的問題。

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