題目：

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

Input

第一行是兩個(gè)整數(shù)N和K，以一個(gè)空格分隔。
以下K行每行是三個(gè)正整數(shù) D，X，Y，兩數(shù)之間用一個(gè)空格隔開(kāi)，其中D表示說(shuō)法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。

Output

只有一個(gè)整數(shù)，表示假話的數(shù)目。

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

分析：

整理模板，發(fā)現(xiàn)自己博客連這道經(jīng)典算法題都木有，orz，貼一下吧，這道題雖然是種類并查集的模板，但自己不喜歡用種類并查集%3這種方法寫(xiě)，就直接貼吧。

#include<stdio.h> #include<string.h> int m,n,dp[150010]; int f(int x) {return x==dp[x]?x:f(dp[x]); } void dfs(int x,int y) {int xx=f(x);int yy=f(y);if(xx!=yy)dp[yy]=xx;return ; } int bfs(int x,int y) {int xx=f(x);int yy=f(y);if(xx!=yy)return 0;return 1; } int main() {scanf("%d%d",&m,&n);int a,b,c;for(int i=1; i<=m*3; i++)dp[i]=i;int ans=0;while(n--){scanf("%d%d%d",&c,&a,&b);if(a>m||b>m){ans++;continue;}if(c==1)/*設(shè)定a吃a+m,a+m吃a+2*m,a+2*m吃a*/{if(bfs(a,b+m)||bfs(a,b+2*m))/*如果a和b是同類，則a和b+m,b+2*m，一定不是同類*/ans++;else{dfs(b,a);dfs(b+m,a+m);dfs(b+2*m,a+2*m);}}else if(c==2){if(bfs(a,b)||bfs(a,b+m))/*如果a吃b，則a和b+2*m是同類,a和b，b+m一定不是同類，*/ans++;else{dfs(b+2*m,a);dfs(b,a+m);dfs(b+m,a+2*m);}}}printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的食物链 POJ - 1182的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。