XCPC Notes

Appearance

发布时间：2025-03-18

前言 ​

经常听到题解出现“一种b开头的生成树算法”，因此记录一下有关完全图的用到该算法的题目

算法步骤 ​

  1. 对于每个连通块内部的点，求出连向外部连通块的最小边，更新本连通块的最小边
  2. 枚举每个连通块，然后用最小边连接外部的连通块
  3. 重复1、2操作，直至连通块变为1 在这里插入图片描述

复杂度 ​

因为每次连通块数量至少减半，因此最多迭代log⁡n\log n次

对于普通最小生成树而言，每次迭代需要枚举边的数量mm,复杂度为O(mlog⁡n)O(m\log n)，并查集的复杂度忽略不计

用途 ​

当然不是用来求普通最小生成树问题的，稠密图有primprim，稀疏图有kruscalkruscal，基本都完爆boruvkaboruvka

那么有什么用呢？

这个算法通常是求完全图的最小/最大生成树，两个点的边权不会直接给你，而是给出一个公式，而且数据范围通常大于等于1e51e5会把n2n^2做法卡掉，此时你需要预处理一些东西，来快速更新连通块连向外部的最小/最大边

有的题目也可能只是用了该算法的思想，实际并不会执行该算法

模板(最小生成树) ​

cpp
vector<array<int,3>> edges;
int mn[N],id[N],vis[M],n,m;
void boruvka(){
    DSU dsu(n+1);
    int ans=0,cnt=0;
    while(1){
        fill(mn,mn+n+1,INF);
        fill(id,id+n+1,-1);
        for(int i=0;i<m;i++){
            if(vis[i])continue;
            auto &[u,v,w]=edges[i];
            int fu=dsu.find(u),fv=dsu.find(v);
            if(fu==fv)continue;
            if(w<mn[fu])mn[fu]=w,id[fu]=i;
            if(w<mn[fv])mn[fv]=w,id[fv]=i;
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(mn[i]==INF)continue;
            if(dsu.merge(edges[id[i]][0],edges[id[i]][1])){
                ans+=mn[i];
                vis[id[i]]=1;
                cnt++;
                flag=true;
            }
        }
        if(!flag)break;
    }
    if(cnt==n-1)cout<<ans<<"\n";
    else cout<<"orz\n";
}

例题 ​

CF888G ​

题意：

给定nn个节点的无向完全图，ii和jj的边权为ai⊕aja_i \oplus a_j，求解最小生成树

思路：

  • 此题只用到了boruvkaboruvka的思想
  • 首先想到异或最小值就是01−trie01-trie上与当前值公共路径最大的一条边，因此利用该算法思想自底向上合并
  • 当两条路走到他们的最近公共祖先时，就需要合并
  • 当前节点有两个儿子，我们预处理出每颗子树包含的叶子(每个叶子对应一个值)，合并的时候遍历sizesize更小的节点，利用这些叶子的值去查找与另一条路径叶子节点异或的最小值，遍历小sizesize相当于小的合并大的，根据启发式合并的复杂度，每个叶子会均摊寻找log⁡n\log n次，每次寻找需要从头到尾遍历一次01−trie01-trie，因此总复杂度为O(nlog⁡nlog⁡V)O(n \log n \log V),VV为值域
  • 值得注意的是本题不启发式合并(即随便选择一条路径，而不是选择sizesize更小的)也能通过，有可能是01−trie01-trie本身的原因很难构造出极端的数据，因此启发式合并也就没有必要了，分析出来的复杂度只是理论上界值，实际会小很多
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int tr[N*30][2],idx,a[N],val[N*30],siz[N*30],n;
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int v=x>>i&1;
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    val[p]=x;
}
int query(int x,int u){
    int p=0;
    for(int i=30;i>=0;i--){
        int v=x>>i&1;
        if(tr[p][v]&&p!=u)p=tr[p][v];
        else p=tr[p][v^1];
    }
    return val[p];
}
int dfs_pre(int p){
    if(!tr[p][0]&&!tr[p][1]){
        return siz[p]=1;
    }
    if(tr[p][0])siz[p]+=dfs_pre(tr[p][0]);
    if(tr[p][1])siz[p]+=dfs_pre(tr[p][1]);
    return siz[p];
}
int cal(int p,int u){
    if(!tr[p][0]&&!tr[p][1]){
        return val[p]^query(val[p],u);
    }
    if(tr[p][0]&&tr[p][1])return min(cal(tr[p][0],u),cal(tr[p][1],u));
    if(tr[p][0])return cal(tr[p][0],u);
    return cal(tr[p][1],u);
}
int dfs(int p){
    int ans=0;
    if(tr[p][0])ans+=dfs(tr[p][0]);
    if(tr[p][1])ans+=dfs(tr[p][1]);
    if(tr[p][0]&&tr[p][1]){
        if(siz[tr[p][0]]<siz[tr[p][1]])ans+=cal(tr[p][0],p);
        else ans+=cal(tr[p][1],p);
    }
    return ans;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);
    dfs_pre(0);
    cout<<dfs(0);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

UOJ176 新年的繁荣 ​

题意：

nn个点的无向完全图，ii和jj的边权为ai&aja_i \& a_j，ai<2ma_i \lt 2^m,求最大生成树

1≤n≤105,1≤m≤181 \leq n \leq 10^5 ,1 \leq m \leq 18

思路 ​

kruscal做法 ​

本来是练习的，但是发现值域很小，普通kruscalkruscal也能做，那就先分析一下kruscalkruscal如何做吧

  • 很容易想到的是对于相等的数，直接互相连接即可，对于不相等的数，都开一个桶，装入一些值，这些值AND起来有可能等于当前值的一些数，我们枚举每个值的子集就可以做到
  • 然后从大到小枚举每个桶，将桶里面的值合并
  • 时间复杂度O(3m)O(3^m)，然后会发现在1s的时限内无法过去，只拿了70分

O(3m)O(3^m)做法:

cpp
void solve(){ 
    int n,m;
    cin>>n>>m;
    vector<int> a(1<<m);
    int ans=0;
    DSU dsu(1<<m);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(a[x])ans+=x;
        a[x]=x;
    }
    vector<int> v[1<<m];
    for(int s=0;s<1<<m;s++){
        if(!a[s])continue;
        for(int t=s;t;t=(t-1)&s){
            v[t].push_back(s);
        }
    }
    for(int i=(1<<m)-1;i>=0;i--){
        for(auto &x:v[i]){
            if(dsu.merge(v[i][0],x))ans+=i;
        }
    }
    cout<<ans<<"\n";
}
  • 继续分析发现对于每个数，我们可以直接继承只比当前二进制位多1位不同的值，这样就可以降低到O(m2m)O(m2^m)
cpp
void solve(){ 
    int n,m;
    cin>>n>>m;
    vector<int> a(1<<m);
    int ans=0;
    DSU dsu(1<<m);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(a[x])ans+=x;
        a[x]=x;
    }
    for(int i=(1<<m)-1;i>=0;i--){
        for(int j=0;j<m&&!a[i];j++){
            a[i]=a[i|(1<<j)];
        }
        for(int j=0;j<m;j++){
            if(!a[i|(1<<j)])continue;
            if(dsu.merge(a[i],a[i|(1<<j)]))ans+=i;
        }
    }
    cout<<ans<<"\n";
}

boruvka做法 ​

相比于kruscalkruscal，该做法就复杂多了，看官方题解好像是官方一开始也没想到kruscalkruscal的做法

正题：

使用trie求解，考虑一个问题，如何知道当前节点可以走，即当前节点有和当前查询点不在一个连通块的。

我们可以对每个节点维护一个最大编号和最小编号，只有最大编号=最小编号=当前编号时，这个节点才不能走，我们每迭代一轮就重构一次trie树

然后就是需要考虑如何去用trie求解,因为走当前节点相同位数是不一定优的；因此我们需要重构一下trie数，把每个节点的1分支路径都合并到0分支路径；这样，1能走就走，否则走0就行

每个儿子都会被祖先遍历一次，最多mm个祖先，复杂度为O(m2m)O(m2^m)

本质上是当前集合包含了他的超集，因此理论上SOSDP也是可以的，但是不熟不会写。。

总复杂度为O((n+m2m)log⁡n)O((n+m2^m)\log n)

cpp
const int BIT=18;
int tr[N*BIT][2],idx,minv[N*BIT],maxv[N*BIT];
void insert(int x,int pos){
    int p=0;
    for(int i=BIT-1;i>=0;i--){
        int v=x>>i&1;
        if(!tr[p][v])tr[p][v]=++idx,minv[idx]=INF,maxv[idx]=-INF;
        minv[tr[p][v]]=min(minv[tr[p][v]],pos);
        maxv[tr[p][v]]=max(maxv[tr[p][v]],pos);
        p=tr[p][v];
    }
}
int merge(int x,int y){
    if(!y)return x;
    if(!x)x=++idx,minv[idx]=INF,maxv[idx]=-INF;
    minv[x]=min(minv[x],minv[y]);
    maxv[x]=max(maxv[x],maxv[y]);
    tr[x][0]=merge(tr[x][0],tr[y][0]);
    tr[x][1]=merge(tr[x][1],tr[y][1]);
    return x;
}
void dfs_pre(int p){
    if(tr[p][0])dfs_pre(tr[p][0]);
    if(tr[p][1])dfs_pre(tr[p][1]);
    tr[p][0]=merge(tr[p][0],tr[p][1]);
}
PII query(int x,int pos){
    int p=0,res=0;
    for(int i=BIT-1;i>=0;i--){
        int v=x>>i&1;
        if(tr[p][v]&&v&&(minv[tr[p][v]]!=pos||maxv[tr[p][v]]!=pos)){
            res+=1<<i;
            p=tr[p][1];
        }
        else p=tr[p][0];
    }
    return {res,maxv[p]==pos?minv[p]:maxv[p]};
}
void clear(){
    for(int i=0;i<=idx;i++)maxv[i]=-INF,minv[i]=INF,tr[i][0]=tr[i][1]=0;
    idx=0;
}
void solve(){ 
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    int ans=0;
    DSU dsu(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<int> mx(n+1,INF),mxpos(n+1);
    while(1){
        clear();
        mx.assign(n+1,-INF);
        for(int i=1;i<=n;i++)insert(a[i],dsu.find(i));
        dfs_pre(0);
        for(int i=1;i<=n;i++){
            int fi=dsu.find(i);
            auto [res,pos]=query(a[i],fi);
            if(mx[fi]<res)mx[fi]=res,mxpos[fi]=pos;
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(dsu.find(i)==i&&dsu.merge(i,mxpos[i])){
                ans+=mx[i];
                flag=true;
            }
        }
        if(!flag)break;
    }
    cout<<ans<<"\n";
}

MST and Rectangles ​

在这里插入图片描述

  • 由于是二维计数问题，因此可以使用扫描线，每次迭代都重新建一颗线段树
  • 计算的时候，我们扫描线从下网上扫，枚举纵坐标(即节点)，线段树上维护最小次小值，那么必定可以找到除当前连通块的最小值
  • 每次迭代都是nlog⁡nn \log n,因此总复杂度O(nlog⁡2n)O(n \log^2n)
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=1e5+10,M=2e5+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
struct Node{
    array<int,2> fi,se;
    int tag=0;
    Node operator+(const Node &t){
        Node res;
        res.fi=min(fi,t.fi);
        res.se={INF,-1};
        if(res.fi[1]!=fi[1])res.se=min(res.se,fi);
        if(res.fi[1]!=se[1])res.se=min(res.se,se);
        if(res.fi[1]!=t.fi[1])res.se=min(res.se,t.fi);
        if(res.fi[1]!=t.se[1])res.se=min(res.se,t.se);
        return res;
    };
};
vector<Node> t;
void pushup(int p){
    t[p]=t[p<<1]+t[p<<1|1];
}
void build(int p,int l,int r){
    if(l==r){
        t[p].fi={0,dsu.find(l)};
        t[p].se={INF,-1};
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void pushtag(int p,int x){
    t[p].fi[0]+=x;
    t[p].se[0]+=x;
    t[p].tag+=x;
}
void pushdown(int p){
    if(t[p].tag){
        pushtag(p<<1,t[p].tag);
        pushtag(p<<1|1,t[p].tag);
        t[p].tag=0;
    }
}
void modify(int p,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
        pushtag(p,x);
        return;
    }
    pushdown(p);    
    int mid=l+r>>1;
    if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);
    if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,x);
    pushup(p);
}
void solve(){ 
    int n,m;
    cin>>n>>m;
    vector<array<int,4>> lines;
    for(int i=0;i<m;i++){
        int x1,x2,y1,y2,w;
        cin>>x1>>x2>>y1>>y2>>w;
        lines.push_back({x1,x2,y1,w});
        lines.push_back({x1,x2,y2+1,-w});
        lines.push_back({y1,y2,x1,w});
        lines.push_back({y1,y2,x2+1,-w});
        int X1=max(x1,y1),X2=min(x2,y2);
        // if(X1<=X2){
        //     lines.push_back({X1,X2,X1,-w});
        //     lines.push_back({X1,X2,X2+1,w});
        // }
    }
    sort(lines.begin(),lines.end(),[](array<int,4> a,array<int,4> b){
        return a[2]<b[2];
    });
    dsu.init(n+1);
    vector<array<int,2>> mn;
    int ans=0;
    while(1){
        t=vector<Node>(n<<2);
        build(1,1,n);
        mn.assign(n+1,{INF,-1});
        for(int i=1,j=0;i<=n;i++){
            while(j<lines.size()&&lines[j][2]==i)modify(1,1,n,lines[j][0],lines[j][1],lines[j][3]),j++;
            int fi=dsu.find(i);
            if(t[1].fi[1]==fi)mn[fi]=min(mn[fi],t[1].se);
            else mn[fi]=min(mn[fi],t[1].fi);
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(dsu.find(i)==i&&mn[i][1]!=-1&&dsu.merge(i,mn[i][1])){
                flag=true;
                ans+=mn[i][0];
            }
        }
        if(!flag)break;
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

U523839 星际联邦 ​

有 nn 个行星，第 ii 个行星的 uu 元素含量为 uiu_i（uiu_i 可以是负数），搭建 1≤i<j≤n1 \leq i<j \leq n 间利用 uu 元素的快速通行轨道的代价为 uj−uiu_j-u_i，为保证连通性，需要让新铺设的 uu 元素轨道使得各行星连成一棵树。

那么满足要求的最少代价是多少呢？

思路：

  • 对于每一个点，他向外连接的最小边就是min⁡(ai−mxi,mni−ai)\min(a_i-mx_i,mn_i-a_i)，mximx_i为前缀最大值，mnimn_i为后缀最小值，这都可以每次迭代预处理出来
  • 时间复杂度O(nlog⁡n)O(n\log n)
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=4e6+10,M=2e5+10;
const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
int a[N],n;
array<int,2> mx[N],mn[N];
void update(){
    array<int,2> fi={-INF,-1},se={-INF,-1}; 
    for(int i=1;i<=n;i++){
        int f=dsu.find(i);
        if(fi[0]==-INF){
            mx[i]={-INF,-1};
            fi={a[i],f};
            continue;
        }
        if(fi[1]==f){
            mx[i]=se;
            if(a[i]>fi[0])fi[0]=a[i];
        }
        else{
            mx[i]=fi;
            if(a[i]>fi[0]){
                se=fi;
                fi={a[i],f};
            }
            else if(a[i]>se[0])se={a[i],f};
        }
    }
    fi={INF,-1},se={INF,-1};
    for(int i=n;i>=1;i--){
        int f=dsu.find(i);
        if(fi[0]==INF){
            mn[i]={INF,-1};
            fi={a[i],f};
            continue;
        }
        if(fi[1]==f){
            mn[i]=se;
            if(a[i]<fi[0])fi[0]=a[i];
        }
        else{
            mn[i]=fi;
            if(a[i]<fi[0]){
                se=fi;
                fi={a[i],f};
            }
            else if(a[i]<se[0])se={a[i],f};
        }
    }
}
void boruvka(){
    dsu.init(n+1);
    int ans=0,cnt=0;
    update();
    while(1){
        vector<array<int,2>> MN(n+1,{INF,-1});
        for(int i=1;i<=n;i++){
            int fi=dsu.find(i);
            if(mx[i][0]!=-INF){
                MN[fi]=min(MN[fi],{a[i]-mx[i][0],mx[i][1]});
            }
            if(mn[i][0]!=INF){
                MN[fi]=min(MN[fi],{mn[i][0]-a[i],mn[i][1]});
            }
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(dsu.find(i)==i){
                if(MN[i][0]==INF)continue;
                if(dsu.merge(i,MN[i][1])){
                    ans+=MN[i][0];
                    cnt++;
                    flag=true;
                }
            }
        }
        if(!flag)break;
        update();
    }
    cout<<ans<<"\n";
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    boruvka();
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

CF1305G ​

在这里插入图片描述

  • 即ai&aj=0a_i \& a_j=0就可以连一条边，如果ii向jj连边边权为aia_i
  • 建立一个虚点，an+1=0a_{n+1}=0，假设他已经被拉进集合，那么问题可以转化为ii与jj的边权为ai+aja_i+a_j，答案为最大生成树减去∑i=1n+1ai\sum_{i=1}^{n+1} a_i
  • 因此题目转化为求最大生成树，且满足ai&aj=0a_i \& a_j=0才有边
  • 每次迭代可以使用SOSdp，汇集当前数二进制子集所有边的最大值。然后再枚举一遍，如果当前数为x，那么和他按位与为0的值，可以用一个二进制全1的数异或上x，得到最大集，这个数包含了所有与x按位与为0的数，同样的记录最大次大值，因此就可以求出来连向外面的最大边
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=3e6+10,M=2e5+10;
const int INF=1e18;
// const int mod=998244353;
const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int LIMIT=1<<18;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
int n,a[N];
struct Node{
    int val,id;
} best[LIMIT][2],large[N];
void trans(Node x[2],Node y[2]){
    for(int i=0;i<2;i++){
        if(x[0].val<y[i].val||(x[0].val==y[i].val&&x[0].id!=y[i].id)){
            if(x[0].id!=y[i].id)x[1]=x[0];
            x[0]=y[i];
        }
        else if(x[1].val<y[i].val&&y[i].id!=x[0].id)x[1]=y[i];
    }
}
void solve(){ 
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>a[i],ans-=a[i];
    dsu.init(n+2);
    while(1){
        for(int i=0;i<LIMIT;i++)best[i][0]=best[i][1]={-1,-1};
        for(int i=1;i<=n+1;i++){
            int id=dsu.find(i);
            int x=a[i];
            if(best[x][0].val==-1)best[x][0]={x,id};
            else if(best[x][1].val==-1&&best[x][0].id!=id)best[x][1]={x,id};
        }
        for(int i=0;i<18;i++){
            for(int j=0;j<LIMIT;j++){
                if(j>>i&1){
                    trans(best[j],best[j^(1<<i)]);
                }
            }
        }
        for(int i=1;i<=n+1;i++)large[i]={-1,-1};
        for(int i=1;i<=n+1;i++){
            int s=(LIMIT-1)^a[i];
            int id=dsu.find(i);
            Node tmp;
            if(id==best[s][0].id)tmp=best[s][1];
            else tmp=best[s][0];
            if(tmp.val!=-1&&tmp.val+a[i]>large[id].val)large[id]={tmp.val+a[i],tmp.id};
        }
        bool flag=false;
        for(int i=1;i<=n+1;i++){
            if(dsu.find(i)==i&&large[i].val!=-1&&dsu.merge(i,large[i].id)){
                ans+=large[i].val;
                flag=true;
            }
        }
        if(!flag)break;
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

AT_keyence2019_e Connecting Cities ​

在这里插入图片描述

  • 思路和写法都与星际那题一样，不再赘诉
  • 复杂度为O(nlog⁡n)O(n \log n)
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
int n,a[N],D;
array<int,2> pre[N],suf[N];
void update(){
    array<int,2> MN1={INF,-1},MN2={INF,-1};
    for(int i=1;i<=n;i++){
        int f=dsu.find(i);
        if(MN1[0]==INF){
            pre[i]=MN1;
            MN1={a[i]-i*D,f};
            continue;
        }
        if(f==MN1[1]){
            pre[i]=MN2;
            if(a[i]-i*D<MN1[0])MN1[0]=a[i]-i*D;
        }
        else{
            pre[i]=MN1;
            if(a[i]-i*D<MN1[0]){
                MN2=MN1;
                MN1={a[i]-i*D,f};
            }
            else if(a[i]-i*D<MN2[0])MN2={a[i]-i*D,f};
        }
    }
    MN1=MN2={INF,-1};
    for(int i=n;i>=1;i--){
        int f=dsu.find(i);
        if(MN1[0]==INF){
            suf[i]=MN1;
            MN1={a[i]+i*D,f};
            continue;
        }
        if(f==MN1[1]){
            suf[i]=MN2;
            if(a[i]+i*D<MN1[0])MN1[0]=a[i]+i*D;
        }
        else{
            suf[i]=MN1;
            if(a[i]+i*D<MN1[0]){
                MN2=MN1;
                MN1={a[i]+i*D,f};
            }
            else if(a[i]+i*D<MN2[0])MN2={a[i]+i*D,f};
        }
    }
}
void solve(){
    cin>>n>>D;
    for(int i=1;i<=n;i++)cin>>a[i];
    dsu.init(n+1);
    vector<array<int,2>> minv(n+1,{INF,-1});   
    int ans=0; 
    while(1){
        update();
        minv.assign(n+1,{INF,-1});
        for(int i=1;i<=n;i++){
            int f=dsu.find(i);
            if(pre[i][0]!=INF)minv[f]=min(minv[f],{a[i]+i*D+pre[i][0],pre[i][1]});
            if(suf[i][0]!=INF)minv[f]=min(minv[f],{a[i]-i*D+suf[i][0],suf[i][1]});
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(dsu.find(i)==i&&minv[i][1]!=-1&&dsu.merge(i,minv[i][1])){
                ans+=minv[i][0];
                flag=true;
            }
        }
        if(!flag)break;
    }
    cout<<ans<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

AT_cf17_final_j Tree MST ​

在这里插入图片描述

待补。。

CF1550F Jumping Around ​

在这里插入图片描述

待补。。

相关的完全图题目，与boruvka无关 ​

CF2082F ​

在这里插入图片描述

  • 对于每个可能的xx，只考虑它本身不考虑它的倍数，肯定是连接第一个大于它并且出现在数组的数。如果考虑倍数，那么就枚举当前值ii的倍数，向所有第一个大于它当前倍数的数连边，由于是调和级数，枚举复杂度为O(nlog⁡n)O(n \log n)
  • 然后从小到大连边，复杂度为O(α(n)nlog⁡n)O(\alpha(n)n \log n)
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=5e5+10,M=2e5+10;
// const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void solve(){ 
    int n;
    cin>>n;
    int mx=0;
    vector<int> a(n);
    for(auto &i:a)cin>>i,mx=max(mx,i);
    vector<int> vis(mx+1),ne(mx+10,-1);
    for(auto &i:a)vis[i]=1;
    vector vec(2,vector (mx+1,vector<int>()));
    for(int i=mx;i>=1;i--){
        if(vis[i])ne[i]=i;
        else ne[i]=ne[i+1];
    }
    for(int i=1;i<=mx;i++){
        if(!vis[i])continue;
        for(int j=2*i;j<=mx;j+=i){
            if(ne[j]==-1)continue;
            int x=ne[j];
            vec[0][x-j].push_back(i);
            vec[1][x-j].push_back(x);
        }
        if(i!=mx){
            int x=ne[i+1];
            vec[0][x-i].push_back(i);
            vec[1][x-i].push_back(x);
        }
    }
    DSU dsu(mx+1);
    int ans=0;
    for(int i=0;i<=mx;i++){
        for(int j=0;j<vec[0][i].size();j++){
            if(dsu.merge(vec[0][i][j],vec[1][i][j]))ans+=i;
        }
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

总结 ​

纯板子题就是和星际联邦这种可以用前后缀扫一遍出答案的写法，通常的话会结合一些高级数据结构或dp，一般都是需要维护最大/次大或者最小/次小值来获取非相同连通块的最小值。也有仅仅只是利用了他的思想的题例如CF888G。

Wenwei Lin · 2022 — 2025