【并查集】noi2001食物链

P2024 [NOI2001]食物链

//这是一道比我年纪大的题啊啊啊啊啊QAQ

加权并查集三倍并查集好厉害qwq

图源洛谷题解

贴代码qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n, k, opt, x, y, ans = 0, f[150010];
 5 void init() { for(int i = 1; i <= n*3; i++) f[i] = i;}
 6 //开三倍并查集，一倍存自己的同类， 二倍存自己的猎物， 三倍存自己的天敌 
 7 int find(int x) {
 8     if(x != f[x]) f[x] = find(f[x]);
 9     return f[x];
10 } 
11 int merge(int u, int v) {
12     int r1 = find(u), r2 = find(v);
13     f[r1] = r2;
14 }
15 int main() {
16     scanf("%d%d",&n,&k);
17     init();
18     while(k--) {
19         scanf("%d%d%d",&opt,&x,&y);
20         if(x>n||y>n) ans++;
21         else if(opt == 1) {
22             if(find(x+n)==find(y)||find(x+2*n)==find(y)) ans++;
23             //如果x的猎物是y 或者 如果x的天敌是y 
24             else {
25                 merge(x, y), merge(x+n, y+n), merge(x+2*n, y+2*n);
26             }
27         }
28         else {
29             if(x == y) ans++;
30             else {
31                 if(find(x)==find(y)||find(x+2*n)==find(y)) {ans++; continue;}
32                 //如果x和y是同类 如果x的天敌是y  
33                   merge(x+n,y), merge(x,y+2*n), merge(x+2*n,y+n);
34                   //如果是真话， 则x的猎物是y， x和y的天敌是同类， x的天敌和y的猎物是同类  
35             }
36         }
37     }    
38     printf("%d",ans);
39     return 0;
40 }

加油加油ヾ(◍°∇°◍)ﾉﾞ

总之岁月漫长，然而值得期待。