次小生成树

abensyl · 2023-10-31 18:46:06 · 算法·理论

前置知识

回顾求解最小生成树的算法，有两种：kruskal 和 prim。

Kruskal 最小生成树。
Prim 最小生成树。

次小生成树：边权和大于等于最小生成树的另一颗树，也就是边权之和第二小的生成树，有严格次小生成树和非严格次小生成树两类之分；
非严格次小生成树：若求得的另一颗树与最小生成树权值可以相等，也就是只要大于等于即可；
严格次小生成树：边权之和严格大于最小生成树的且权值最小的树，也就是严格第二小的生成树。

非严格次小生成树

思路

求次小生成树的第一步就是先求解最小生成树，那么在生成最小生成树后，很容易想到如下操作：

说明：以下的描述中均是 n 点 m 边无向图，n 就表示点数，m 表示图的总边数，树边表示原最小生成树上的边，非树边即不是原最小生成树上的边。

进行替换，对于替换操作，实际上就是对于生成树，找到一个非树边（不在原最小生成树中的边），把它与最小生成树中的边进行替换，那么，我们把非树边加入原最小生成树中，很明显，原本的最小生成树会变成一个 n 点 n 边的基环树，对于这棵基环树，若要求次小生成树，应找到形成的环中除了加入边之外的最长边，将其删除，这样就可以将基环树破为树了，只需要枚举每一条非树边，然后对于形成的环进行枚举，即可得到答案。

简而言之，假如原图是 G=(V,E)，对于一棵最小生成树 T=(V,E')，我们找到一条非树边 e，形象地说，e\in E 并且 e \notin E'，那么将这条边 e 与 T 合并，得到新的图 G'=(V,E'\cup\{e\})，这个图有 n 个点 n 个边，而且连通，所以它是一棵基环树，所谓基环树，就是只含有一个环的树形结构，也就是说，如果将这个环缩成一个点，那么这会变成一个树形结构，然而还有另一种定义方式更有助于最小生成树的理解，基环树就是由一棵树加入一条边形成的结构，如下图：

基环树的形成过程是树加边，那么如果基环树减掉一个边就会变回一棵树，前提是，减掉的边必须在环上，也就是说，如果我们任意去掉换上的一条边，那么就会得到一棵新树，如果我们把刚刚加进来的边 e 给去掉了，那么就变回了原来的最小生成树，简称“没用”，想得到最小生成树，就得删掉一条除了 e 以外的环上边，我们可以考虑枚举原本环上有哪些点，然后删除环上的一条边，为了让生成树是非严格次小的，关键就在于一个“小”，我们要删掉的环上除了 e 以外最大的边。

然后我们枚举每一个 e，检测生成环，然后进行替换即可。

correctness

至少有一条边在次小生成树中而不在最小生成树中。

证明：显然。
证明次小生成树一定包含 n-2 条最小生成树边和仅一条非树边组成的，而不是大于一条非树边：

由结论 1 我们可以得到某条在次小生成树而不在最小生成树上的边，我们称它为 e。
显然 e 是条无用边，因为它不在 MST 上。
对于最小生成树，我们添加一个非树边，这个非树边会和原生成树形成一个环，很显然，加入的这条非树边 e 肯定是整个环中边权最大的边，也就是说，对于每一个原图中的环，最小生成树破环的方式都一定是最优的，那么，也就是说，我们往环中加边只会让答案更劣，所以就需要加的边尽可能的少，又因为结论 1，至少有一条变为非树边，所以由此可知，有且仅有一条非树边在次小生成树中。
任意无用边的对应最小生成树肯定不是一开始求的 MST。

证明：显然。

efficiency

对于 MST 的求解，可以用 kruskal 或 prim 通过 O(m\log n) 或 O(m\log m) 的时间复杂度解决，用哪种取决于图的稠密程度。

对于非树边，进行枚举，然后进行求环。

以下代码采用 kruskal，时间复杂度为 O(m\log m+nm)：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct node {
    int to,nx,wt;
} eg[N<<1];
int hd[N],tot=0;
void adeg(int u,int v,int w) {
    eg[++tot]={v,hd[u],w},hd[u]=tot;
}
struct dsu {
    int f[N];
    void init(int n) { for(int i=1;i<=n;++i) f[i]=i; }
    int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
    void merge(int x,int y) { f[find(x)]=find(y); }
} d;
struct edge {
    int u,v,w;
} ed[N<<1];
bitset<N<<1> in;
int kruskal(int n,int m) {
    d.init(n); int sum=0;
    sort(ed+1,ed+m+1,[&](edge x,edge y){ return x.w<y.w; });
    for(int i=1;i<=m;++i) {
        int u=ed[i].u,v=ed[i].v,w=ed[i].w;
        if(d.find(u)==d.find(v)) continue;
        d.merge(u,v);
        in[i]=true;
        adeg(u,v,w),adeg(v,u,w);
        sum+=w;
    } return sum;
}
int dep[N],f[N][18];
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=1;i<18;++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=hd[u];i;i=eg[i].nx)
        if(eg[i].to!=fa) dfs(eg[i].to,u);
}
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=17;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    for(int i=17;i>=0;--i)
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    if(u==v) return u;
    return f[u][0];
}
vector<int> stk;
void findpath(int u,int d) {
    if(u==d) return;
    for(int i=hd[u];i;i=eg[i].nx) {
        int to=eg[i].to;
        if(dep[to]>dep[u]) continue;
        stk.push_back(eg[i].wt);
        findpath(to,d);
    }
}
int replace(int u,int v) {
    int lc=lca(u,v),mx=-1e18;
    stk.clear(),findpath(u,lc);
    for(auto c:stk) mx=max(mx,c);
    stk.clear(),findpath(v,lc);
    for(auto c:stk) mx=max(mx,c);
    return mx;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i) {
        int u,v,w;
        cin>>u>>v>>w;
        ed[i]={u,v,w};
    } int val=kruskal(n,m);
    if(val==-1) {
        cout<<"-1\n";
        return 0;
    } int res=1e18;
    dfs(1,0);
    for(int i=1;i<=m;++i) {
        if(in[i]) continue;
        int u=ed[i].u,v=ed[i].v,w=ed[i].w;
        int c=replace(u,v);
        res=min(res,val+w-c);
    } cout<<res<<'\n';
    return 0;
}

优化

考虑生成环，如果加入的非树边 e=(u,v)，那么它和原本树边形成一个环，就是 u\rightarrow\operatorname{lca}(u,v)\rightarrow v\rightarrow u，\operatorname{lca}(u,v) 可以用倍增或树链剖分求出，树上特定路径中边长最大值也可以用倍增或树链剖分计算。

利用倍增或树链剖分进一步优化时间复杂度，将时间复杂度优化为 O(m\log ⁡n+m\log ⁡n)，即在每条重链上记录最大值或者在倍增数组中建立 st 表记录，代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, INF = 1e15;
int16_t st[N][19],f[N][19],n,m,dep[N];
struct edge {
    int u,v,w;bool in=false;
} e[N*3];
struct dsu {
    int f[N];
    void init(int n) { for(int i=1;i<=n;++i) f[i]=i; }
    int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
    void merge(int x,int y) { f[find(x)]=find(y); }
} d;
struct egnd {
    int to,nx,wt;
} eg[N<<1];
int hd[N],tot;
void adeg(int u,int v,int w) {
    eg[++tot]={v,hd[u],w};
    hd[u]=tot;
}
int kruskal() {
    int res=0;d.init(n);
    sort(e+1,e+m+1,[&](edge x,edge y){ return x.w<y.w; });
    for(int i=1;i<=m;++i) {
        if(d.find(e[i].u)==d.find(e[i].v)) continue;
        d.merge(e[i].u,e[i].v);
        res+=e[i].w,e[i].in=1;
        adeg(e[i].u,e[i].v,e[i].w),
        adeg(e[i].v,e[i].u,e[i].w);
    } return res;
}
void dfs(int u,int fa) {
    f[u][0]=fa,dep[u]=dep[fa]+1;
    for(int i=1;i<=18;++i) {
        f[u][i]=f[f[u][i-1]][i-1];
        st[u][i]=min(st[u][i-1],st[f[u][i-1]][i-1]);
    }
    for(int i=hd[u];i;i=eg[i].nx) {
        int v=eg[i].to;
        if(v==fa) continue;
        st[v][0]=eg[i].wt;
        dfs(v,u);
    }
}
int LCA(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    for(int i=18;i>=0;--i)
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return (u==v)?u:f[u][0];
}
int findpath(int u,int v) {
    int res=0;
    for(int i=18;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) res=min(res,st[u][i]),u=f[u][i];
    return res;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;++i) cin>>e[i].u>>e[i].v>>e[i].w;
    int lk=kruskal(),res=9e18;
    dfs(1,0);
    for(int i=1;i<=m;++i) {
        if(e[i].in) continue;
        int lca=LCA(e[i].u,e[i].v);
        int zc=min(findpath(e[i].u,lca),findpath(e[i].v,lca));
        res=min(res,lk+e[i].w-zc);
    } cout<<res<<'\n';
    return 0;
}

练习题

Timus1416. Confidential

严格次小生成树

思路

刚才在非严格次小生成树中，我们的删边做法是：找到形成的环中除了加入边之外的最长边，将其删除。

那么，如果我们删去的这条边与加入的那条边权值相同，那么实际上就等于改变了树的构造，但实际上还是最小生成树，所以不严格。

如要求解严格次小生成树，那么必须保证替换的边与删除的边权值不同，所以，如果最大值与替换边的权值相同，那么我们就需要用严格次大值来替换，不过这个时候，严谨的说，我们需要的是严格次大值，只要改变一下刚才 st 表的构造，同时记录最大值和严格次大值即可，代码如下：

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, INF = 1e15;
pii st[N][19];
int f[N][19],n,m,dep[N];
struct edge {
    int u,v,w;bool in=false;
} e[N*3];
struct dsu {
    int f[N];
    void init(int n) { for(int i=1;i<=n;++i) f[i]=i; }
    int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
    void merge(int x,int y) { f[find(x)]=find(y); }
} d;
struct egnd {
    int to,nx,wt;
} eg[N<<1];
int hd[N],tot;
void adeg(int u,int v,int w) {
    eg[++tot]={v,hd[u],w};
    hd[u]=tot;
}
int kruskal() {
    int res=0;d.init(n);
    sort(e+1,e+m+1,[&](edge x,edge y){ return x.w<y.w; });
    for(int i=1;i<=m;++i) {
        if(d.find(e[i].u)==d.find(e[i].v)) continue;
        d.merge(e[i].u,e[i].v);
        res+=e[i].w,e[i].in=1;
        adeg(e[i].u,e[i].v,e[i].w),
        adeg(e[i].v,e[i].u,e[i].w);
    } return res;
}
pii merge(pii x,pii y) {
    pii res={0,0};
    if(x.first<y.first) swap(x,y);
    res.first=x.first;
    if(y.first==x.first) res.second=max(x.second,y.second);
    else res.second=max(y.first,x.second);
    return res;
}
void dfs(int u,int fa) {
    f[u][0]=fa,dep[u]=dep[fa]+1;
    for(int i=1;i<=18;++i) {
        f[u][i]=f[f[u][i-1]][i-1];
        st[u][i]=merge(st[u][i-1],st[f[u][i-1]][i-1]);
    }
    for(int i=hd[u];i;i=eg[i].nx) {
        int v=eg[i].to;
        if(v==fa) continue;
        st[v][0]={eg[i].wt,0};
        dfs(v,u);
    }
}
int LCA(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    for(int i=18;i>=0;--i)
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return (u==v)?u:f[u][0];
}
pii findpath(int u,int v) {
    pii res={0,0};
    for(int i=18;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) res=merge(res,st[u][i]),u=f[u][i];
    return res;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;++i) cin>>e[i].u>>e[i].v>>e[i].w;
    int lk=kruskal(),res=9e18;
    dfs(1,0);
    for(int i=1;i<=m;++i) {
        if(e[i].in) continue;
        int lca=LCA(e[i].u,e[i].v);
        pii zc=merge(findpath(e[i].u,lca),findpath(e[i].v,lca));
        if(zc.first!=e[i].w) res=min(res,lk+e[i].w-zc.first);
        else res=min(res,lk+e[i].w-zc.second);
    } cout<<res<<'\n';
    return 0;
}

板子题：【洛谷 P4180】[BJWC2010] 严格次小生成树。 这道题有坑，注意重边和自环，它们不能被加入次小生成树！

例题

题目链接：Codeforces GYM 101889，Problem I Imperial Roads；
题解：Imperial Roads。

题目链接：Codeforces GYM 100803, Problem F, There is No Alternative；
题解：There Is No Alternative。