首页 > 代码库 > POJ 1182 食物链 [并查集 带权并查集 开拓思路]
POJ 1182 食物链 [并查集 带权并查集 开拓思路]
传送门
P - 食物链
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64uAppoint description:
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），输出假话的总数。
现有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。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
100 71 101 1 2 1 22 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 }
POJ 1182 食物链 [并查集 带权并查集 开拓思路]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。