带权并查集

· · 个人记录

一般来说带权并查集由这样几个东西（当然更多情况因题而异）

  1. 集合大小

  2. 每个点到集合super_father的距离

  3. 源点父亲

代码实现就是在基础的并查集上加点料。

int getfa(int x){
   //类似回溯，从后往前更新
    if(x!=fa[x]){
        int i=fa[x];
        fa[x]=getfa(fa[x]);
        val[x]+=val[i];
    }
    return fa[x];
}

合并操作类似，但是更为灵活，可以用向量法则简化计算。

（合并操作实际只用添加一个fa，其他的点在需要用时会在getfa里完成更新）

例题1 [NOI2002]银河英雄传说

十分的板子，就是记录上面说的那些东西，query的时候统计s就行了

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,fa[500005],s[500005],siz[500005];
int getfa(int x){
    if(fa[x]==x) return x;
    int k=fa[x];
    fa[x]=getfa(fa[x]);
    s[x]+=s[k];
    siz[x]=siz[fa[x]];
    return fa[x];
}
void merge(int l,int r){
    int fal=getfa(l);
    int far=getfa(r);
    fa[fal]=far;
    s[fal]+=siz[far];
    siz[fal]+=siz[far];
    siz[far]=siz[fal];
}
int qu(int l,int r){
    int fal=getfa(l);
    int far=getfa(r);
    if(fal!=far) return -1;
    else return abs(s[l]-s[r])-1;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i,s[i]=0,siz[i]=1;
    for(int i=1;i<=n;i++){
        int l,r;
        char ss;cin>>ss>>l>>r;
        if(ss=='M'){
            merge(l,r);
        }
        else {
            cout<<qu(l,r)<<"\n";
        }
    }
    return 0;
}

例题2 How Many Answers Are Wrong

不难发现，若把图画出来，只有新的两点在原图中已经联通的时候才能确定其值，否则合并即可。

（一点trick，因为题目给出的左闭右闭，我们可以l--变为左闭右开，这样方便直接连图）

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int getint(){
    int summ=0,f=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')f=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}
const int M=1e6;
int fa[M],val[M],n,m,ans=0;
int getfa(int x){
    if(x!=fa[x]){
        int xx=fa[x];
        fa[x]=getfa(fa[x]);
        val[x]+=val[xx];
    }
    return fa[x];
}
signed main(){
    while(cin>>n>>m){
        for(int i=0;i<=n;i++) fa[i]=i,val[i]=0;ans=0;
        while(m--){
            int l,r,value;
            l=getint();r=getint();value=getint();
            l--;
            int fal=getfa(l),far=getfa(r);
            if(fal==far){
                if(val[l]-val[r]!=value) ans++; 
            }
            else{
                val[fal]=-val[l]+value+val[r];
                fa[fal]=far;
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

例题3 [NOI2001]食物链

可以用三个并查集暴力。

也可以用带权并查集更加优雅的解决。

我们把 相同、吃、被吃 看做0、1、2 ，然后发现同一个连通块内两点距离对3取模即使其关系。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int getint(){
    int summ=0,f=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')f=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}
const int M=1e6;
int fa[M],val[M],n,m,ans=0;
int getfa(int x){
    if(x!=fa[x]){
        int i=fa[x];
        fa[x]=getfa(fa[x]);
        val[x]+=val[i];val[x]%=3;
    }
    return fa[x];
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++) fa[i]=i,val[i]=0;ans=0;
    while(m--){
        int l,r,op;
        op=getint();l=getint();r=getint();
        if(l>n||r>n||(l==r&&op==2)){
            ans++;continue;
        } 
        int fal=getfa(l),far=getfa(r);
        if(fal==far){
            if(op==1) if((((val[l]-val[r])%3+3)%3)!=0) ans++; 
            if(op==2) if((((val[l]-val[r])%3+3)%3)!=1) ans++; 
        }
        else{
            if(op==1) val[fal]=-val[l]+val[r];val[fal]%=3;
            if(op==2) val[fal]=-val[l]+val[r]+1;val[fal]%=3;
            fa[fal]=far;
        }
    }
    cout<<ans<<endl;    
    return 0;
}