http://poj.org/problem?id=1182

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://ke.baidu.com/view/f11c8fbd551810a6f524866f.html

//我主要參考了這個博客//http://blog.csdn.net/wmn_wmn/article/details/7416370

題解：

主要不是做這個題，而是用到的算法，先說下這題的坑，輸入while（scanf("%d%",&n,&k)!=EOF)就WA，只有一組

測試數據，另外不能用cin,因為k的范圍為100000；超時。現在還不怎么懂為什么可以用向量的方法做，只能暫且記下來了。

#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; int n,k,sum; struct node {int fa;int relation; } q[50001]; void init() {for(int i=1; i<=n; i++){q[i].fa=i;q[i].relation=0;}sum=0; } int findx(int x) {int temp;if(x==q[x].fa){return x;}temp=q[x].fa;q[x].fa=findx(temp);//雖然和以前的寫法不同，但路徑壓縮的思想是一樣的q[x].relation=(q[temp].relation+q[x].relation)%3;return q[x].fa; } int main() {int d,x,y;scanf("%d%d",&n,&k);init();while(k--){scanf("%d%d%d",&d,&x,&y);if(x>n||y>n){sum++;continue;}if(d==2&&x==y){sum++;continue;}int fx,fy;fx=findx(x);fy=findx(y);if(fx!=fy){q[fy].fa=fx;q[fy].relation=(q[x].relation+d-1+3-q[y].relation)%3;}else{if(d==1&&q[x].relation!=q[y].relation){sum++;continue;}else if(d==2&&(3-q[x].relation+q[y].relation)%3!=1){sum++;continue;}}}printf("%d\n",sum);return 0; }

?大神總結的算法，果斷粘貼

解題思路：這道題是并查集題目中的經典。。。而且比普通并查集提高了一個檔次，下面在基礎并查集的前提上講解并查集的真正用法。基礎回顧：find()函數找根結點的兩種寫法如下：第一種遞歸：int find(int x) { return x == pre[x] ? x : find(pre[x]); } 第二種：int find(int x) { int root, temp; root = x; while(root != pre[root]) root = pre[root]; while(x != root) { temp = pre[x]; pre[temp] = root; x = temp; } return root; } 上面2種是最基本的查找操作。下面我們通過這道題來講解一下并查集的深層次應用。輸入:動物個數n以及k句話,接著輸入k行,每一行形式為:d x y,在輸入時可以先判斷題目所說的條件2和3,即:1>若(x>n||y>n):即當前的話中x或y比n大,則假話數目sum加1.2>若(x==2&&x==y):即當前的話表示x吃x,則假話數目sum加1.而不屬于這兩種情況外的話語要利用并查集進行判斷當前的話是否與此前已經說過的話相沖突.struct node { int parent; //p[i].parent表示節點i的父節點 int relation; //p[i].relation表示節點i與其父節點(即p[i].parent)的關系 }p[50010]; 此處relation有三種取值(假設節點x的父節點為rootx,即p[x].parent=rootx)：p[x].relation=0 ……表示節點x與其父節點rootx的關系是：同類p[x].relation=1 ……表示節點x與其父節點rootx的關系是：被根結點吃p[x].relation=2 ……表示節點x與其父節點rootx的關系是：吃根結點初始化函數為:void init(int n) { int i; for(i = 1;i <= n; ++i) { p[i].parent = i; //初始時集合編號就設置為自身 p[i].relation = 0; //因為p[i].parent=i,即節點i的父親節點就是自身,所以此時節點i與其父親節點的關系為同類(即p[i].relation=0) } } 下面詳細講解并查集的兩個重要操作:查找和合并.查找操作：在查找時因為節點不僅有父親節點域,而且還有表示節點與其父親節點的關系域,查找過程中對父親節點域的處理和簡單的并查集處理一樣,即在查找過程中同時實現路徑壓縮,但正是由于路徑壓縮,使得表示節點與其父親節點的關系域發生了變化,所以在路徑壓縮過程中節點和其對應的父節點的關系域發生了變化(因為路徑壓縮之前節點x的父親節點為rootx的話,那么在路徑壓縮之后節點x的父親節點就變為了節點rootx的父親節點rootxx,所以此時p[x].relation存儲的應該是節點x與現在父親節點rootxx的關系),此處可以畫圖理解一下:很明顯查找之前節點x的父親節點為rootx,假設此時p[x].relation=1(即表示x的父親節點rootx吃x)且p[rootx].relation=0(即表示rootx和其父親節點rootxx是同類),由這兩個關系可以推出rootxx吃x,而合并以后節點x的父親節點為rootxx(實現了路徑壓縮),且節點x的父親節點rootxx吃x,即查找之后p[x].relation=1。合并操作：在將元素x與y所在的集合合并時,假設元素x所在的集合編號為rootx,元素y所在的集合編號為rooty,合并時直接將集合rooty掛到集合rootx上,即p[rooty].parent=rootx,此時原來集合rooty中的根節點rooty的關系域也應隨之發生變化,因為合并之前rooty的父親節點就是其自身,故此時p[rooty].relation=0,而合并之后rooty的父親節點為rootx,所以此時需判斷rootx與rooty的關系,即更新p[rooty]的值,同理畫圖理解:
此時假設假設p[x].relation=0(即x與rootx的關系是同類),p[y].relation=1(即rooty吃y),則有:1>輸入d=1時,即輸入的x和y是同類,則有上述關系可以推出rooty吃rootx,即p[rooty].relation=2;2>輸入d=2時,即輸入的x吃y,則有上述關系可以推出rooty與rootx是同類(因為rooty吃y,x吃y,則rooty與x是同類,又rootx與x是同類),即p[rooty].relation=0;當然,這只是一種可能,其它的可能情況和上面一樣分析。當元素x與元素y在同一集合時,則不需要合并,因為此時x與y的父親節點相同,可以分情況討論:1>d=1時,即x與y是同類時,此時要滿足這要求,則必須滿足p[x].relation=p[y].relation,這很容易推出來.2>d=2時,即表示x吃y,此時要滿足這要求,則也必須滿足一定的條件,如x和root是同類(即p[x].relation=0),此時要滿足x吃y,則必須滿足root吃y,即p[y].relation=1,可以像上面一樣畫圖來幫助理解.關系域更新： 當然，這道題理解到這里思路已經基本明確了，剩下的就是如何實現，在實現過程中，我們發現，更新關系域是一個很頭疼的操作，網上各種分析都有，但是都是直接給出個公式，至于怎么推出來的都是一筆帶過，讓我著實頭疼了很久，經過不斷的看discuss，終于明白了更新操作是通過什么來實現的。下面講解一下仔細再想想，rootx-x 、x-y、y-rooty，是不是很像向量形式?于是我們可以大膽的從向量入手：tx ty| |x ~ y對于集合里的任意兩個元素x，y而言，它們之間必定存在著某種聯系，因為并查集中的元素均是有聯系的（這點是并查集的實質，要深刻理解），否則也不會被合并到當前集合中。那么我們就把這2個元素之間的關系量轉化為一個偏移量（大牛不愧為大牛！~YM）。由上面可知： x->y 偏移量0時 x和y同類x->y 偏移量1時 x被y吃x->y 偏移量2時 x吃y有了這個假設，我們就可以在并查集中完成任意兩個元素之間的關系轉換了。不妨繼續假設，x的當前集合根節點rootx，y的當前集合根節點rooty，x->y的偏移值為d-1（題中給出的詢問已知條件）(1)如果rootx和rooty不相同，那么我們把rooty合并到rootx上，并且更新relation關系域的值（注意：p[i].relation表示i的根結點到i的偏移量！！！！（向量方向性一定不能搞錯））此時 rootx->rooty = rootx->x + x->y + y->rooty，這一步就是大牛獨創的向量思維模式上式進一步轉化為：rootx->rooty = (relation[x]+d-1+3-relation[y])%3 = relation[rooty]，（模3是保證偏移量取值始終在[0,2]間）(2)如果rootx和rooty相同(即x和y在已經在一個集合中，不需要合并操作了，根結點相同)，那么我們就驗證x->y之間的偏移量是否與題中給出的d-1一致此時 x->y = x->rootx + rootx->y上式進一步轉化為：x->y = (3-relation[x]+relation[y])%3，若一致則為真，否則為假。分析到這里，這道題已經從思想過渡到實現了。剩下的就是一些細節問題，自己處理一下就好了。PS：做完這題，就可以去秒了大部分基礎的并查集了，嘿嘿大笑代碼如下：#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 50010 struct node { int pre; int relation; }; node p[N]; int find(int x) //查找根結點 { int temp; if(x == p[x].pre) return x; temp = p[x].pre; //路徑壓縮 p[x].pre = find(temp); p[x].relation = (p[x].relation + p[temp].relation) % 3; //關系域更新 return p[x].pre; //根結點 } int main() { int n, k; int ope, a, b; int root1, root2; int sum = 0; //假話數量 scanf("%d%d", &n, &k); for(int i = 1; i <= n; ++i) //初始化 { p[i].pre = i; p[i].relation = 0; } for(int i = 1; i <= k; ++i) { scanf("%d%d%d", &ope, &a, &b); if(a > n || b > n) //條件2 { sum++; continue; } if(ope == 2 && a == b) //條件3 { sum++; continue; } root1 = find(a); root2 = find(b); if(root1 != root2) // 合并 { p[root2].pre = root1; p[root2].relation = (3 + (ope - 1) +p[a].relation - p[b].relation) % 3; } else { if(ope == 1 && p[a].relation != p[b].relation) { sum++; continue; } if(ope == 2 && ((3 - p[a].relation + p[b].relation) % 3 != ope - 1)) { sum++; continue;} } } printf("%d\n", sum); return 0; }

?

總結

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

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