526互联

并查集的具体应用 CF1213G CF444E [HNOI2005]狡猾的商人

发布时间 2023-06-22 22:28:17作者: DPD

每当我们看到“最大值最小”“路径上的最大最小值”等字眼时，我们就可以考虑并查集。

我们可以尝试把这些问题转化为某种意义上按单调顺序的合并，利用并查集求解答案。以下时两例并查集的巧妙应用。

CF1213G Path Queries

注意“最大权值不大于q”，加上允许离线，我们可以把边按照权值排序，并一条一条加边，即合并两端点所在的连通块。设当前边端点为 u，v，权值为w，因为排过序，所以一条边的端点所在联通块内的边权一定比w小，也就是说，最大权值等于q的简单路径就会有siz【u】*siz【v】条，也就是当前边对答案的贡献。最后用前缀和合并一下，就能得到答案。这道题做法很多，点分治，Kruskal 重构树等均可，但我认为并查集是最好写的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+55;
int siz[N],fa[N],m,n;
struct edge{
    int u,v,w;
}e[N<<1];
int q[N],ans[N];
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
bool cmp(edge a,edge b){
    return a.w<b.w;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    sort(e+1,e+n,cmp);
    for(int i=1;i<=m;i++) cin>>q[i];
    //sort(q+1,q+1+m);
    for(int i=1;i<n;i++){
        //ans[e[i].w]=ans[e[i-1].w];
        int u=e[i].u,v=e[i].v;
        int x=find(u),y=find(v);
        ans[e[i].w]+=siz[x]*siz[y];
        fa[y]=x;siz[x]+=siz[y];    
    }
    for(int i=1;i<N;i++) ans[i]+=ans[i-1];
    for(int i=1;i<=m;i++){
        cout<<ans[q[i]]<<" ";
    }
}
View Code

 

CF444E DZY Loves Planting

此题正解是二分答案+网络流，并且出现在我校网络流专题考试中。然而，除了CF官方题解，似乎没有哪个大冤种拿网络流写（除了考场上的我）

注意到题干中的min，求最大值的最小值最大，且离线，和上一题套路一样，把边按照边权从小到大排序，一个一个加。则连通块内边权一定小于当前边，即两个连通块之间的路径最大值就是这个边的权值，我们只需判断是否合法即可。对于当前已经合并的点，我们都需要给他配一个未合并的点，这样 g（x，y）才会 大于等于w，如果都能分配到，则该答案合法。

形式化的，设siz[u]表示u的连通块的大小，sum为所有x[i]之和，val[u]表示u的连通块内x[i]之和，那么，如果 $size[u]\le sum-val[u]$ ，则该答案合法。我们甚至完全不用二分，只需要按边权枚举每一条边即可，在加边，也就是合并区间的时候，更新fa，siz，val的值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e4+6;
int n,m,fa[N],siz[N],val[N],sum;
//val 表示 该连通块中xi的和 
int find(int u){
    if(fa[u]==u) return u;
    return fa[u]=find(fa[u]);
}
struct edge{
    int u,v,w;
}e[N<<1];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+1+n-1,cmp);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=n;i++){
        cin>>val[i];
        sum+=val[i];
    }
    for(int i=1;i<=n-1;i++){
        int u=e[i].u,v=e[i].v;
        int x=find(u),y=find(v);
        fa[x]=y;
        siz[y]+=siz[x];val[y]+=val[x];
        if(siz[y]>sum-val[y]){
            cout<<e[i].w;
            return 0;
        }
    }
    cout<<e[n-1].w;
    return 0;
}
View Code

 

[HNOI2005]狡猾的商人

此题的标准做法是差分约束，但是用带权并查集也可以。我觉得他们本质是相同的，而显然带权并查集更好写。

对于此题而言，每条信息（l，r，w），将l，r放入一个集合中，并维护c[l]=s[fa]-s[l],c[r]=s[fa]-s[r],若fa[l]==fa[r],则判断 c[l]-c[r] 与 w 是否相等即可。（这里要用路径压缩，fa也就是该集合的根）

#include<bits/stdc++.h>
using namespace std;
int fa[666],cha[666],T,n,m,x,y,z,p;
int s[666];
int find(int x){//带权并查集 
    if(x==fa[x]) return fa[x];
    else{
        int t=find(fa[x]);
        cha[x]+=cha[fa[x]];
        fa[x]=t;
        return fa[x];
    }
}
int main(){
    cin>>T;
    while(T--){
        p=1;
        cin>>n>>m;
        for(int i=0;i<=n;i++){fa[i]=i;cha[i]=0;}
        for(int i=1;i<=m;i++){
            cin>>x>>y>>z;
            x--;//qian zhui he
            if(find(x)!=find(y)){
                cha[fa[y]]=cha[x]-cha[y]-z;
                fa[fa[y]]=fa[x];
            }else{
                if(cha[x]-cha[y]!=z) p=0;
            }
        }
        if(p) cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
    return 0;
}
View Code