P2024- [NOI2001]食物链

傷城~ 2023-06-01 08:47 1阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define MOD 1000000007
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 
    24 const int maxn = 150033;
    25 int par[maxn]; 
    26 int high[maxn]; 
    27 int n,K;
    28 void init(int n)
    29 {
    30     _for(i,1,3*(n+1))
    31     {
    32         par[i] = i;
    33         high[i] = 0;
    34     }
    35 } 
    36 
    37 int find(int x)
    38 {
    39     return par[x] == x ? x : par[x] = find(par[x]);
    40 }
    41 
    42 void unite(int x,int y)
    43 {
    44     x = find(x);y = find(y);
    45     if(x==y) return ;
    46     
    47     if(high[x]<high[y])
    48         par[x] = y;
    49     else
    50     {
    51         par[y] = x;
    52         if(high[x]==high[y])
    53             high[x] ++;
    54     }
    55 }
    56 
    57 bool same(int x,int y)
    58 {
    59     return find(x) == find(y);
    60 }
    61 bool judgeFalse(int a,int b,int c)
    62 {
    63     if(1==a)
    64     {
    65         if(same(b+n,c) || same(b+2*n,c))
    66             return true;
    67     }
    68     else
    69     {
    70         if(same(b,c) || same(b,c+(2*n)))
    71             return true;
    72     }
    73     return false;
    74 }
    75 
    76 int main()
    77 {
    78     n = read(),K = read();
    79     init(n);
    80     int ans = 0;
    81     _for(i,1,K+1)
    82     {
    83         int a,b,c;
    84         a = read(),b = read(),c = read();
    85         if(b>n || c>n)
    86         {    ans ++;continue;}
    87         else if(a==2 && b==c)
    88         {    ans ++;continue;}
    89         if(judgeFalse(a,b,c))
    90         {    ans ++;continue;}
    91         else if(a==1)
    92             unite(b,c),unite((b+n),(c+n)),unite((b+n*2),(c+n*2));
    93         else if(a==2)
    94             unite(b,(c+n)),unite((b+n),(c+n*2)),unite((b+n*2),c);
    95     }
    96     printf("%d\n",ans);
    97     return 0;
    98 }

转载于:https://www.cnblogs.com/Asurudo/p/11551595.html