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

?/********************************************************
此道題目 前天看的時候一點頭緒都沒有，看了他人的解題報告后
也幾乎看不懂，但是首先做了兩道并查集的基礎題目POJ1611，與
POJ2524，熟悉并查集的結構，又做了兩道并查集的拓展題目
POJ2492與1703,，在充分了解并可以熟悉運用并查集后，此題
便可迎刃而解了，也通過此題發現了自學的訣竅“循序漸進”，
剛剛AC掉食物鏈問題，有些小激動，遂發此感慨，呵呵~~~
********************************************************/

View Code 1 #include<iostream>
2 usingnamespace std;
3
4 int N,K,relation,a,b,count;
5 int p[50010],r[50010];//p[]為父親數組，
6 //r[]為x與p[x]的關系數組
7 //0代表同類，1代表x吃父親p[x]
8 //1代表父親p[x]吃x
9
10 /*******************************************************/
11 //初始化函數
12 void make(){
13 for(int i=1;i<=N;i++){
14 p[i]=i;
15 r[i]=0;
16 }
17 }
18 /******************************************************/
19 //查找根節點（祖宗）的函數，采用遞推壓縮路徑
20 //使得每一個節點都指向祖宗
21 int find(int x){
22 int temp=p[x];//p[x]之后要被修改，先記下x的父親值
23 if(x==p[x])return p[x];
24
25 p[x]=find(p[x]);//遞推壓縮路徑，都指向了根節點
26 r[x]=(r[x]+r[temp])%3;//關系修改
27
28 return p[x];
29 }
30 /*******************************************************/
31 //合并
32 void unionSet(int x,int y,int px,int py){
33 p[px]=py;
34 r[px]=(r[y]-r[x]+3+relation-1)%3;
35 //關于三處的關系修改于判斷，本人一開始采用枚舉的方式，
36 //不過如果枚舉的話，每次使用倒要if（3*3=）九次,很是
37 //啰嗦，之后總結出公式，不過可以用進行嚴格向量法證明
38 /*
39 if(relation==1){
40 //r[px]=(r[y]-r[x])%3;
41 if(r[x]==r[y]){r[px]=0;return;}
42 if(r[x]==0){r[px]=r[y];return;}
43 if(r[y]==0){r[px]=r[x];return;}
44 if(r[x]==1){r[px]=1;return;}
45 if(r[y]==1){r[px]=2;return;}
46 }
47 if(relation==2){
48 //r[px]=(r[y]-r[x]+1)%3;
49
50 if(r[x]==0&&r[y]==0){}
51 if(r[x]==0&&r[y]==1){}
52 if(r[x]==0&&r[y]==2){}
53 if(r[x]==0&&r[y]==)
54 */
55 }
56
57 /*******************************************************/
58 int main(){
59 cin>>N>>K;
60 int pa,pb;
61 count=0;
62 make();
63 while(K--){
64 scanf("\n%d%d%d",&relation,&a,&b);
65 pa=find(a);
66 pb=find(b);
67 //輸入數據有矛盾可以直接判斷
68 if(a>N||b>N||(relation==2&&a==b)){count++;continue;}
69 //pa!=pb,則說明，a與b還未建立關系，所以肯定不會
70 //產生矛盾
71 if(pa!=pb){unionSet(a,b,pa,pb);continue;}
72 //如果產生關系，但是根據已存在的r[a]與r[b]算出的
73 //a與b之間的關系與輸入的relation不相符，則矛盾
74 if((r[a]-r[b]+3)%3!=(relation-1)){count++;continue;}
75 }
76 cout<<count<<endl;
77 }

轉載于:https://www.cnblogs.com/liushang0419/archive/2011/04/26/2029841.html

總結

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

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