带权并查集

突然发现自己不知道这是什么东西。。。

感觉好像就是在并查集的基础上多维护了一些有用的量

然后做了一道大水题

poj 1182 食物链

题解可见这个博客写的挺清楚

我就插个代码在这

 1 //poj 1182
 2 
 3 ll read()
 4 {
 5     ll x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch=='-')f=-1;
10         ch=getchar();
11     }
12     while(ch>='0'&&ch<='9')
13     {
14         x=x*10+ch-'0';
15         ch=getchar();
16     }
17     return x*f;
18 }
19 
20 void print(ll x)
21 {
22     if(x<0)putchar('-'),x=-x;
23     short a[20]= {},sz=0;
24     while(x>0)a[sz++]=x%10,x/=10;
25     if(sz==0)putchar('0');
26     for(ll i=sz-1; i>=0; i--)putchar('0'+a[i]);
27 }
28 
29 const ll mod=1e9+7;
30 
31 int n,k;
32 int fa[111111];
33 int sy[111111];
34 
35 int fnd(int x){
36     if(fa[x]==x) return x;
37     else{
38         int nw=fa[x];
39         fa[x]=fnd(fa[x]);
40         sy[x]=(sy[nw]+sy[x])%3;
41         return fa[x];
42     }
43 }
44 
45 bool check(int tp,int x,int y){
46     if(x>n || y>n) return 0;
47     if(tp==1 && x==y) return 0;
48     int fx=fnd(x),fy=fnd(y);
49     if(fx==fy)
50         if((sy[x]-sy[y]+3)%3==tp) return 1;
51         else return 0;
52         
53     return 1;
54 }
55 
56 void uni(int tp,int x,int y){
57     int fx=fnd(x),fy=fnd(y);
58     if(fx!=fy){
59         fa[fx]=fy;
60         sy[fx]=(sy[y]-sy[x]+tp+3)%3;
61     }
62 }
63 
64 int main(){
65     #ifdef LZT
66         freopen("in","r",stdin);
67     #endif
68     n=read();k=read();
69     
70     for(int i=1;i<=n;i++)
71         fa[i]=i;
72     
73     int ans=0;
74     while(k--){
75         int tp=read(),x=read(),y=read();
76         tp--;
77         if(check(tp,x,y))
78             uni(tp,x,y);
79         else
80             ans++;
81     }
82     
83     print(ans);
84     puts("");
85     return 0;
86 }

View Code