傳送門 P -?食物鏈 Time Limit:1000MS?????Memory Limit:10000KB?????64bit IO Format:%I64d & %I64u Submit?Status?Practice?POJ 1182 Appoint description:?System Crawler? (2015-01-27)

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

?

先吐槽一下關于多組樣例的問題，閑話也不多說，這題網上大牛各種神奇的題解都有，第一份代碼是常規帶權并查集的做法，不多談，我主要想談一下第二份代碼的思路。

如果我們換一個思路，把1--n看成與自身同類的集合，1+n--2*n看成自己吃的集合，1+2*n--3*n看成吃自己的集合，那么問題便簡單多了~~~

?

1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<string> 12 13 #define N 50005 14 #define M 105 15 #define mod 1000000007 16 //#define p 10000007 17 #define mod2 1000000000 18 #define ll long long 19 #define LL long long 20 #define eps 1e-6 21 #define inf 100000000 22 #define maxi(a,b) (a)>(b)? (a) : (b) 23 #define mini(a,b) (a)<(b)? (a) : (b) 24 25 using namespace std; 26 27 int n,m; 28 int f[N]; 29 int r[N]; 30 int ans; 31 32 void ini() 33 { 34 ans=0; 35 int i; 36 for(i=0;i<=n;i++){ 37 f[i]=i; 38 r[i]=0; 39 } 40 } 41 42 int find(int x) 43 { 44 int fa; 45 if(f[x]!=x) 46 { 47 fa=find(f[x]); 48 r[x]=(r[x]+r[ f[x] ])%3; 49 f[x]=fa; 50 } 51 return f[x]; 52 } 53 54 void merge(int x,int y,int d) 55 { 56 int a,b; 57 a=find(x); 58 b=find(y); 59 if(a==b){ 60 return; 61 } 62 f[b]=a; 63 r[b]=(3-r[y]+r[x]+d)%3; 64 } 65 66 void solve() 67 { 68 int d,x,y; 69 int a,b; 70 int re; 71 int i; 72 for(i=1;i<=m;i++){ 73 scanf("%d%d%d",&d,&x,&y); 74 if(x>n || y>n){ 75 ans++;continue; 76 } 77 if(d==2 && x==y){ 78 ans++;continue; 79 } 80 a=find(x); 81 b=find(y); 82 re=(3-r[x]+r[y])%3; 83 if(a==b && re!=d-1){ 84 ans++;continue; 85 } 86 //printf(" i=%d\n",i); 87 merge(x,y,d-1); 88 } 89 } 90 91 void out() 92 { 93 printf("%d\n",ans); 94 } 95 96 int main() 97 { 98 //freopen("data.in","r",stdin); 99 //freopen("data.out","w",stdout); 100 //scanf("%d",&T); 101 //for(int ccnt=1;ccnt<=T;ccnt++) 102 //while(T--) 103 //while(scanf("%d%d",&n,&m)!=EOF) 104 scanf("%d%d",&n,&m); 105 { 106 ini(); 107 solve(); 108 out(); 109 } 110 return 0; 111 }

?

?

如果我們換一個思路，把1--n看成與自身同類的集合，1+n--2*n看成自己吃的集合，1+2*n--3*n看成吃自己的集合，那么問題便簡單多了~~~

?

1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<string> 12 13 #define N 50005 14 #define M 105 15 #define mod 1000000007 16 //#define p 10000007 17 #define mod2 1000000000 18 #define ll long long 19 #define LL long long 20 #define eps 1e-6 21 #define inf 100000000 22 #define maxi(a,b) (a)>(b)? (a) : (b) 23 #define mini(a,b) (a)<(b)? (a) : (b) 24 25 using namespace std; 26 27 int n,m; 28 int f[3*N]; 29 int ans; 30 31 void ini() 32 { 33 ans=0; 34 int i; 35 for(i=0;i<=3*n;i++){ 36 f[i]=i; 37 } 38 } 39 40 int find(int x) 41 { 42 int fa; 43 if(f[x]!=x) 44 { 45 fa=find(f[x]); 46 f[x]=fa; 47 } 48 return f[x]; 49 } 50 51 void merge(int x,int y) 52 { 53 int a,b; 54 a=find(x); 55 b=find(y); 56 if(a==b){ 57 return; 58 } 59 f[b]=a; 60 } 61 62 void solve() 63 { 64 int d,x,y; 65 int a,b; 66 int fx,sx; 67 int i; 68 for(i=1;i<=m;i++){ 69 scanf("%d%d%d",&d,&x,&y); 70 if(x>n || y>n){ 71 ans++;continue; 72 } 73 if(d==2 && x==y){ 74 ans++;continue; 75 } 76 a=find(x); 77 b=find(y); 78 fx=find(x+n); 79 sx=find(x+2*n); 80 if(d==1){ 81 if(b==fx || b==sx){ 82 ans++;continue; 83 } 84 else{ 85 merge(x,y); 86 merge(x+n,y+n); 87 merge(x+2*n,y+2*n); 88 } 89 } 90 else{ 91 if(b==a || b==sx){ 92 ans++;continue; 93 } 94 else{ 95 merge(x+n,y); 96 merge(x+2*n,y+n); 97 merge(x,y+2*n); 98 } 99 } 100 } 101 } 102 103 void out() 104 { 105 printf("%d\n",ans); 106 } 107 108 int main() 109 { 110 //freopen("data.in","r",stdin); 111 //freopen("data.out","w",stdout); 112 //scanf("%d",&T); 113 //for(int ccnt=1;ccnt<=T;ccnt++) 114 //while(T--) 115 //while(scanf("%d%d",&n,&m)!=EOF) 116 scanf("%d%d",&n,&m); 117 { 118 ini(); 119 solve(); 120 out(); 121 } 122 return 0; 123 }

?

轉載于:https://www.cnblogs.com/njczy2010/p/4263305.html

總結

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

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