G8016 [GESP202509 八级] 最小生成树 题解

知识点：最小生成树、最近公共祖先、并查集、替换边。

解题思路

Kruskal求一棵MST。非树边被删除不改变答案；对树边，需要最小跨割替换边。将非树边按权升序处理，用LCA找树上路径，跳跃并查集为每条尚未赋值的路径树边设置首个替代权。

为什么正确

添加非树边产生唯一环，环上任一树边都可被它替换；升序首次覆盖给出每个割的最小替代边，删除该树边后据割性质得到最优新树。

易错点

无替代边时输出-1；并查集在建MST后须重新初始化用于跳过已处理树边，不能混用两阶段状态。

复杂度

时间O(m log m+(n+m)log n)保守界，空间O(m+n log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    struct E {
        int u,v,id;
        long long w;
    }
    ;
    vector<E>e(m),sorted;
    for(int i=0;i<m;i++) {
        cin>>e[i].u>>e[i].v>>e[i].w;
        e[i].id=i;
    }
    sorted=e;
    sort(sorted.begin(),sorted.end(),[](auto a,auto b){return a.w<b.w;});
    vector<int>dsu(n+1);
    iota(dsu.begin(),dsu.end(),0);
    function<int(int)>f=[&](int u) {
        return dsu[u]==u?u:dsu[u]=f(dsu[u]);
    }
    ;
    vector<int>used(m),pe(n+1);
    vector<vector<pair<int,int>>>g(n+1);
    long long total=0;
    for(auto x:sorted) {
        int u=f(x.u),v=f(x.v);
        if(u==v)continue;
        dsu[u]=v;
        used[x.id]=1;
        total+=x.w;
        g[x.u].push_back({x.v,x.id});
        g[x.v].push_back({x.u,x.id});
    }
    vector<int>p(n+1),dep(n+1),order= {
        1
    }
    ;
    for(int k=0;k<(int)order.size();k++)for(auto [v,id]:g[order[k]])if(v!=p[order[k]]) {
        p[v]=order[k];
        dep[v]=dep[p[v]]+1;
        pe[v]=id;
        order.push_back(v);
    }
    vector<vector<int>>up(18,p);
    for(int k=1;k<18;k++)for(int u=1;u<=n;u++)up[k][u]=up[k-1][up[k-1][u]];
    auto lca=[&](int u,int v) {
        if(dep[u]<dep[v])swap(u,v);
        int dif=dep[u]-dep[v];
        for(int k=0;k<18;k++)if(dif>>k&1)u=up[k][u];
        if(u==v)return u;
        for(int k=17;k>=0;k--)if(up[k][u]!=up[k][v]) {
            u=up[k][u];
            v=up[k][v];
        }
        return p[u];
    }
    ;
    iota(dsu.begin(),dsu.end(),0);
    vector<long long>rep(m,-1);
    for(auto x:sorted)if(!used[x.id]) {
        int z=lca(x.u,x.v);
        for(int start:{x.u,x.v}) {
            int u=f(start);
            while(dep[u]>dep[z]) {
                rep[pe[u]]=x.w;
                dsu[u]=f(p[u]);
                u=f(u);
            }
        }
    }
    for(int i=0;i<m;i++)if(!used[i])cout<<total<<"\n";
    else cout<<(rep[i]<0?-1:total-e[i].w+rep[i])<<"\n";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用20个自行生成的测试点。