題目描述?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　　? 真話

NOI 2001 食物鏈(eat)

類型：圖論 ?難度：3

題意：題面說的很明白，見題目

分析：比1069要難一些的并查集題目，對于每個種類i，用fa[i]記錄其并查集的父節點（同類），用eat[i]記錄它吃誰，用eaten[i]記錄它被誰吃，這樣記錄了一個3物種循環，根據題目分兩種情況：

（1）X和Y是同類，此時，若X吃Y或Y吃X（除了同類只有這兩種關系，因為只有三個物種），則矛盾，結果累加；

若X和Y不存在關系，則需要將X和Y合并為同類，此時，不僅要合并X和Y，還要合并eat[X],eat[Y]和eaten[X],eaten[Y]；

此外，設合并后X和Y這類的根節點為r，還要更新r的eat和eaten值，eat[r]的eat和eaten值，eaten[r]的eat和eaten值，保證信息保留完整

（2）X吃Y，此時，X和Y同類或Y吃X，則矛盾，結果累加；

若X和Y不存在關系，需要合并eat[X]和Y，eaten[Y]和X，eat[Y]和eaten[X]；

和（1）類似，設合并后eat[X]和Y這類的根節點為r，還要更新r的eat和eaten值，eat[r]的eat和eaten值，eaten[r]的eat和eaten值，保證信息保留完整

注意：由于每類的eat和eaten信息都必須存儲在根節點中，但是根節點eat和eaten指向的節點不一定是那一類的根節點，所以寫了兩個findeat和findeaten函數，作用是：先找到當前集合的根節點，然后找到根節點的eat或eaten節點i，再找到這個i在它的集合中的根節點，就能保證eat和eaten關系都操作在根節點層面。

代碼：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int fa[50010],eat[50010],eaten[50010];int mfind(int a) {if(fa[a] != a) fa[a] = mfind(fa[a]);return fa[a]; }int mmerge(int a,int b) {if(!a) return b;if(!b) return a;return (fa[mfind(a)] = mfind(b)); }int findeat(int a) {int ra = mfind(a);int tmp = eat[ra];if(!tmp) return tmp;int rf = mfind(tmp);eat[ra] = rf;return rf; }int findeaten(int a) {int ra = mfind(a);int tmp = eaten[ra];if(!tmp) return tmp;int rf = mfind(tmp);eaten[ra] = rf;return rf; }int main() {int n,k;scanf("%d%d",&n,&k);for(int i=0; i<=n; i++){fa[i] = i;}memset(eat,0,sizeof(eat));memset(eaten,0,sizeof(eaten));int a,b,c;int ans = 0;while(k--){scanf("%d%d%d",&a,&b,&c);if(b>n || c>n || b<=0 || c<=0){ans++;continue;}int rb = mfind(b);int rc = mfind(c);int eb = findeat(rb);int ec = findeat(rc);int etb = findeaten(rb);int etc = findeaten(rc);if(a==1){if(eb==rc || ec==rb || etc==rb || etb==rc){ans++;continue;}fa[rb] = rc;eat[rc] = mmerge(eb,ec);eaten[rc] = mmerge(etb,etc);if(ec) {eaten[ec] = rc;eat[ec] = eaten[rc];}if(etc) {eat[etc] = rc;eaten[etc] = eat[rc];}}else{if(rb==rc || ec==rb || etb==rc){ans++;continue;}eat[rb] = mmerge(eb,rc);eaten[rc] = mmerge(etc,rb);eat[rc] = eaten[rb] = mmerge(etb,ec);int d = eat[rc];if(d){eat[d] = rb;eaten[d] = rc;}}}cout<<ans<<endl; }

總結

以上是生活随笔為你收集整理的wikioi-天梯-提高一等-并查集-1074：食物链的全部內容，希望文章能夠幫你解決所遇到的問題。

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