次小生成树是这样的一个问题:给定一个图,求它生成树中第二小的。

其中生成树的大小为生成树中边权之和。

这个问题有非严格次小和严格次小两种。

算法1

暴力枚举生成树然后排序取第二小。

算法2

可以证明,一定可以在最小生成树中仅替换一条边得到次小生成树。

构造最小生成树,枚举其中每条边,删掉这条边,再在其它边中选最小的可以加进来的一条加进来。

得到的新生成树中取最小值。

那么用kruskal特别方便。

时间复杂度$O(nm)$

当然对于严格次小,选的边一定要比这条边大。

算法3

kruskal构造最小生成树。

枚举每条不在生成树上的边$<u,v>$,把它加上去后就会出现一个环。

那么在原树上找到$<u,v>$之间的路径,删掉最大边,然后加上这条边即可得到新的生成树。

这些里面取最小值即可。

最大边可以通过倍增找lca计算出来。

时间复杂度$O(m\log n)$

对于严格次小生成树,如果最大边和这条边边权一样,就要取严格次大值。

严格次大值也可以倍增计算。

这是洛谷4180 【模板】严格次小生成树 的代码。

/*
Author: CNYALI_LK
LANG: C++
PROG: 4180.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
struct edge{
    ll u,v,w;
};
edge e[333333];
ll fa[102424],use[333333];
ll beg[102424],to[204848],lst[204848],w[204848],dis[102424],en;
ll f[102424][20],mx1[102424][20],mx2[102424][20];
ll e_cmp(edge a,edge b){
    return a.w<b.w;
}

ll find(ll x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add(ll u,ll v,ll wa){
    to[++en]=v;
    lst[en]=beg[u];
    beg[u]=en;
    w[en]=wa;
}
void dfs(ll x,ll fa){
    f[x][0]=fa;
    dis[x]=dis[fa]+1;
    for(ll i=beg[x];i;i=lst[i])if(to[i]!=fa){
        dfs(to[i],x);
    }
    else mx1[x][0]=w[i];
}

void upd(ll &mx1,ll &mx2,ll mxx1,ll mxx2){
    ll nm=max(mx1,mxx1),inm=0;
    if(mx1==nm)chkmax(inm,mx2);
    else chkmax(inm,mx1);
    
    if(mxx1==nm)chkmax(inm,mxx2);
    else chkmax(inm,mxx1);
    mx1=nm;
    mx2=inm;
}
void build(ll n,ll t){
    for(ll j=1;j<=t;++j)for(ll i=1;i<=n;++i){
        f[i][j]=f[f[i][j-1]][j-1];
        mx1[i][j]=mx1[i][j-1];
        mx2[i][j]=mx2[i][j-1];
        upd(mx1[i][j],mx2[i][j],mx1[f[i][j-1]][j-1],mx2[f[i][j-1]][j-1]);
    }
}
ll _lca(edge e){
    ll u=e.u,v=e.v,w=e.w,max1=0,max2=0;
    if(dis[u]<dis[v])swap(u,v); 
    for(ll i=18;~i;--i){
        if(dis[u]-(1<<i)>=dis[v]){
            upd(max1,max2,mx1[u][i],mx2[u][i]);
            u=f[u][i];
        }
    }
    for(ll i=18;~i;--i){
        if(f[u][i]!=f[v][i]){
            upd(max1,max2,mx1[u][i],mx2[u][i]); 
            upd(max1,max2,mx1[v][i],mx2[v][i]); 
            u=f[u][i];
            v=f[v][i];
        }
    }
    if(u!=v){
        ll i=0; 
        upd(max1,max2,mx1[u][i],mx2[u][i]); 
        upd(max1,max2,mx1[v][i],mx2[v][i]); 
        u=f[u][i];
        v=f[v][i];
    }
    if(max1==w)if(max2)return w-max2;else return 0x3f3f3f3f3f3f3f3f;
    else return w-max1;
}

int main(){
#ifdef cnyali_lk
    freopen("4180.in","r",stdin);
    freopen("4180.out","w",stdout);
#endif
    ll n,m;
    n=read();m=read();
    for(ll i=1;i<=m;++i){ 
        e[i].u=read();
        e[i].v=read();
        e[i].w=read();

    }
    sort(e+1,e+m+1,e_cmp);
    for(ll i=1;i<=n;++i)fa[i]=i;
    ll q=n;
    ll sum=0,ans=0x3f3f3f3f3f3f3f3f;
    for(ll i=1;q>1;++i)if(find(e[i].u)!=find(e[i].v)){
        add(e[i].v,e[i].u,e[i].w);
        add(e[i].u,e[i].v,e[i].w);
        sum+=e[i].w;
        fa[find(e[i].u)]=find(e[i].v);  
        use[i]=1;
        --q;
    }
    dfs(1,0);
    build(n,18);
    for(ll i=1;i<=m;++i)if(!use[i]){
        chkmin(ans,sum+_lca(e[i]));
    }
    printf("%lld\n",ans);
    return 0;

}

标签: none

添加新评论