次小生成树讲解

大家好,这里蒟蒻霞客

这次给大家讲解一下次小生成树
想要透彻的理解本篇文章的内容,您需要点亮如下前置技能
1. 掌握至少一种求最小生成树的算法(网上各路神犇的讲解有很多)
2. 会树上倍增(如果不嫌弃,可以看本蒟蒻的博客:传送门


如果您已经掌握了以上技能——我们开始吧!

Chapter 1 Introduction

设 G=(V,E,w)是连通的无向图,T 是图G 的一个最小生成树。如果有另一棵树T1,满
足不存在树T’,ω(T’)<ω(T1) ,则称T1是图G的次小生成树。
次小生成树分为严格次小和非严格次小,如果是严格次小,T1的权值和必须大于T的权值和,而在非严格次小中他们可以相等

Chapter 2 次小生成树的克鲁斯卡尔+树上倍增算法

这个是十分简单的求次小生成树的算法,以下用严格次小来举例
首先我们利用克鲁斯卡尔算法求出图G的最小生成树
我们知道如果我们在最小生成树上添加一条边,这个图一定会出现一个环,如果我们仍想维护树形结构,我们就必须在这个环上删掉一条边
例如我们想要在最小生成树上添加一条x到y的边,我们就必须将原来树上x到y的路径上删掉一条边,而十分显然的是,删掉的边权值越大,新生成树的权值和越小
如果是求次小生成树,我们不但要知道u到v的路径上最大权值,也要知道次大权值,因为最大权值可能与我们新加入的边的权值相等
就此,我们得到了求严格次小生成树的算法全貌:
首先求出最小生成树,设其权值为ans
然后在最小生成树上利用树上倍增,mx_fir[i][j]代表节点i向上跳2^j个节点的最大权值,mx_sec[i][j]代表次大权值
接着考虑每一条不在最小生成树上的边,当前考虑到一条u–>v的边,最小生成树上u到v的路径最大权值为mx1,次大权值为mx2,那么如果加入这条权值为w的边,最小增大权值为mx1!=w?w-mx1:w-mx2
考虑完所有边后,就能得到最小增大权值extra,严格次小生成树的权值即为ans+extra
模板题bzoj1977
下面是蒟蒻的代码:

#include<bits/stdc++.h>
#define MAXN 100010
#define MAXM 300010
#define ll long long
#define inf (0x7fffffff)

using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int dep[MAXN],fa[MAXN][17],mx_fir[MAXN][17],mx_sec[MAXN][17];
int f[MAXN],head[MAXN];
int tot;
int extra=inf,n,m,bin[17],cnt;
ll ans;
struct data{
    int u,v,w;
    int id;
    bool sel;//是否选过
    friend bool operator <(data a,data b){
        return a.w<b.w;
    }
}a[MAXM];
struct edge{
    int to,nxxt,v;
}e[MAXN<<1];
inline void insert(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].v=w;
    e[cnt].nxxt=head[u];
    head[u]=cnt;
}
inline void add(int u,int v,int w){
    insert(u,v,w);insert(v,u,w);
}
inline int getfa(int x){
    while(x!=f[x])x=f[x]=f[f[x]];
    return x;
}
inline void dfs(int x){
    for(register int i=1;i<17;++i){
        if(dep[x]<bin[i])break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
        mx_fir[x][i]=max(mx_fir[x][i-1],mx_fir[fa[x][i-1]][i-1]);
        if(mx_fir[x][i-1]==mx_fir[fa[x][i-1]][i-1])
            mx_sec[x][i]=max(mx_sec[x][i-1],mx_sec[fa[x][i-1]][i-1]);
        else{
            mx_sec[x][i]=min(mx_fir[x][i-1],mx_fir[fa[x][i-1]][i-1]);
            mx_sec[x][i]=max(mx_sec[x][i-1],mx_sec[x][i]);
            mx_sec[x][i]=max(mx_sec[x][i],mx_sec[fa[x][i-1]][i-1]);
        }
    }
    for(register int i=head[x];~i;i=e[i].nxxt){
        int v=e[i].to;
        if(v==fa[x][0])continue;
        fa[v][0]=x;
        mx_fir[v][0]=e[i].v;
        dep[v]=dep[x]+1;
        dfs(v);
    }
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int t=dep[x]-dep[y];
    for(register int i=0;bin[i]<=t;++i)
        if(t&bin[i])x=fa[x][i];
    for(register int i=16;i>=0;--i)
    if(fa[x][i]^fa[y][i])x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
inline void cal(int x,int f,int v){
    int mx1=0,mx2=0;
    int t=dep[x]-dep[f];
    for(register int i=0;bin[i]<=t;++i){
        if(t&bin[i]){
            if(mx_fir[x][i]>mx1){
                mx2=mx1;
                mx1=mx_fir[x][i];
            }
            mx2=max(mx2,mx_sec[x][i]);
            x=fa[x][i];
        }
    }
    extra=min(extra,mx1!=v?v-mx1:v-mx2);
}
inline void solve(int t){
    int x=a[t].u,y=a[t].v,v=a[t].w,f=lca(x,y);
    cal(x,f,v),cal(y,f,v);
}
int main(){
    bin[0]=1;for(register int i=1;i<=16;++i)bin[i]=bin[i-1]<<1;
    memset(head,-1,sizeof(head));
    n=read();m=read();
    for(register int i=1;i<=n;++i)f[i]=i;
    for(register int i=1;i<=m;++i){
        a[i].u=read();a[i].v=read();a[i].w=read();a[i].id=i;
    }
    sort(a+1,a+m+1);
    for(register int i=1;i<=m;++i){
        int u=getfa(a[i].u),v=getfa(a[i].v);
        if(u==v)continue;
        f[u]=v;
        ans+=a[i].w;
        a[i].sel=true;
        add(a[i].u,a[i].v,a[i].w);
        tot++;
        if(tot==n-1)break;
    }
    dfs(1);
    for(register int i=1;i<=m;++i)
    if(!a[i].sel)solve(i);
    printf("%lld\n",ans+(ll)extra);
}

结语

这篇博客就到这里了,如果我写的够好,您应该点亮了次小生成树这一技能
如果有任何问题,欢迎联系我,QQ1145101354,请注明来自我的网站
最后祝您,身体健康
快夸我可爱QvQ

还有想说的。。。

求次小生成树好像还有别的算法,比如lct。。。。或许如果我学了的话以后会更新

3 thoughts on “次小生成树讲解

发表评论

电子邮件地址不会被公开。 必填项已用*标注