次小生成树

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3561 字
求无向图的严格次小生成树边权和
一本通
例
正文

/*
原题：T1555 「一本通 4.4 例 4」次小生成树 (BeiJing 2010)
题意：求无向图的严格次小生成树边权和（边权和严格大于最小生成树的最小者）。
思路：Kruskal 求 MST；倍增预处理树上每段 2^k 路径的最大边权 m1 与严格次大边权 m2。对每条非树边 (u,v,w)，若 w>m1 则用 m1 替换，若 w==m1 且存在 m2 则用 m2 替换，取最小候选。
复杂度：O((N+M) log N)。
易错点：必须是“严格”次小，因此要维护严格次大边权 m2；替换只能在路径上进行。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int n,m;
struct Edge{
    int u,v,w;
};
vector<Edge> edges;
vector<vector<pair<int,int>>> g;
vector<int> dep;
vector<vector<int>> up;
vector<vector<long long>> w1,w2;
int find(int x,vector<int>&fa){
    return fa[x]==x?x:fa[x]=find(fa[x],fa);
}
void dfs(int u,int p,int w){
    up[u][0]=p;
    w1[u][0]=w;
    w2[u][0]=-1;
    for(int i=1;i<LOG;i++){
        int anc=up[u][i-1];
        up[u][i]=up[anc][i-1];
        long long a[4]={w1[u][i-1],w2[u][i-1],w1[anc][i-1],w2[anc][i-1]};
        long long big=-1,sec=-1;
        for(int k=0;k<4;k++){
            if(a[k]>big){ sec=big; big=a[k]; }
            else if(a[k]<big&&a[k]>sec){ sec=a[k]; }
        }
        w1[u][i]=big;
        w2[u][i]=sec;
    }
    for(auto&e:g[u]){
        int v=e.first,wt=e.second;
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u,wt);
    }
}
pair<long long,long long> query(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    long long big=-1,sec=-1;
    for(int i=LOG-1;i>=0;i--){
        if(dep[x]-(1<<i)>=dep[y]){
            long long a[4]={w1[x][i],w2[x][i],big,sec};
            long long nb=-1,ns=-1;
            for(int k=0;k<4;k++){
                if(a[k]>nb){ ns=nb; nb=a[k]; }
                else if(a[k]<nb&&a[k]>ns){ ns=a[k]; }
            }
            big=nb; sec=ns;
            x=up[x][i];
        }
    }
    if(x==y) return {big,sec};
    for(int i=LOG-1;i>=0;i--){
        if(up[x][i]!=up[y][i]){
            long long a[4]={w1[x][i],w2[x][i],w1[y][i],w2[y][i]};
            long long nb=-1,ns=-1;
            for(int k=0;k<4;k++){
                if(a[k]>nb){ ns=nb; nb=a[k]; }
                else if(a[k]<nb&&a[k]>ns){ ns=a[k]; }
            }
            big=nb; sec=ns;
            x=up[x][i];
            y=up[y][i];
        }
    }
    long long a[4]={w1[x][0],w2[x][0],w1[y][0],w2[y][0]};
    long long nb=-1,ns=-1;
    for(int k=0;k<4;k++){
        if(a[k]>nb){ ns=nb; nb=a[k]; }
        else if(a[k]<nb&&a[k]>ns){ ns=a[k]; }
    }
    big=nb; sec=ns;
    return {big,sec};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        edges.push_back({x,y,z});
    }
    sort(edges.begin(),edges.end(),[](Edge a,Edge b){ return a.w<b.w; });
    vector<int> fa(n+1);
    for(int i=1;i<=n;i++) fa[i]=i;
    g.assign(n+1,vector<pair<int,int>>());
    long long sum=0;
    vector<bool> inMST(m,false);
    for(int i=0;i<m;i++){
        int u=edges[i].u,v=edges[i].v,w=edges[i].w;
        int fu=find(u,fa),fv=find(v,fa);
        if(fu!=fv){
            fa[fu]=fv;
            sum+=w;
            inMST[i]=true;
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
    }
    dep.assign(n+1,0);
    up.assign(n+1,vector<int>(LOG,0));
    w1.assign(n+1,vector<long long>(LOG,-1));
    w2.assign(n+1,vector<long long>(LOG,-1));
    dfs(1,0,-1);
    long long ans=1e18;
    for(int i=0;i<m;i++){
        if(inMST[i]) continue;
        int u=edges[i].u,v=edges[i].v,w=edges[i].w;
        auto p=query(u,v);
        long long m1=p.first,m2=p.second;
        if(w>m1) ans=min(ans,sum-m1+w);
        else if(w==m1&&m2!=-1) ans=min(ans,sum-m2+w);
    }
    cout<<ans<<'\n';
    return 0;
}
次小生成树

正文

一本通·提高篇的其它内容
