首页 > 代码库 > poj1182 食物链

poj1182 食物链

2024-07-07 14:08:24   223人阅读

并查集经典题，但是太坑了，数据只有一组，用EOF读入无限WA,我就这么对着正确的代码查了半个多小时，次奥。

把一个结点拆成3个结点分别代表属于A,B,C三类，

对于X，Y同类，有如果XA->YA,XB->YB,XC->YC 所以直接把两两并起来，当然要判断能不能并

对于X吃Y ,有 XA->YB ,XB->YC , XC->YA  ,同上

太坑了！！！！！！！！！！！

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 50010
10 #define maxm 100010
11 using namespace std;
12 int father[maxn*3];
13 int n,m;
14 int cmd[maxm],x[maxm],y[maxm];
15 void init(){
16     for(int i=0;i<maxn*3;++i){
17         father[i]=i;
18     }
19 }
20 int Find(int x){
21     return father[x]==x?x:father[x]=Find(father[x]);
22 }
23 void Union(int x,int y){
24     x=Find(x);
25     y=Find(y);
26     if(x!=y)father[x]=y;
27 }
28 bool same(int x,int y){
29     return Find(x)==Find(y);
30 }
31 void solve(){
32     int ans =0;
33     init();
34     for(int i=0;i<m;++i){
35         int c = cmd[i];
36         int xx = x[i]-1;
37         int yy = y[i]-1;
38         if(xx<0||xx>=n||yy<0||yy>=n){
39             ans++;
40             continue;
41         }
42         else if(c==1){
43             if(same(xx,yy+n)||same(xx,yy+2*n)||same(xx+n,yy)||same(xx+n,yy+2*n)||same(xx+2*n,yy)||same(xx+2*n,yy+n)){
44                 ans++;
45                 continue;
46             }
47             else {
48                 Union(xx,yy);
49                 Union(xx+n,yy+n);
50                 Union(xx+2*n,yy+2*n);
51             }
52         }
53         else{
54             if(same(xx,yy)||same(xx,yy+2*n)||same(xx+n,yy)||same(xx+n,yy+n)||same(xx+2*n,yy+n)||same(xx+2*n,yy+2*n)){
55                 ans++;
56                 continue;
57             }
58             else {
59                 Union(xx,yy+n);
60                 Union(xx+n,yy+2*n);
61                 Union(xx+2*n,yy);
62             }
63         }
64     }
65     printf("%d\n",ans);
66 }
67 int main (){
68     scanf("%d%d",&n,&m);
69     for(int i=0;i<m;++i){
70         scanf("%d%d%d",&cmd[i],&x[i],&y[i]);
71     }
72     solve();
73 }
View Code

 


联系
我们