Problem

BZOJ 入门 OJ P1634
Luogu P4180 BJWC 次小生成树

Introduction

首先讲非严格次小生成树的做法。

先建立权值之和为 $W$ 的最小生成树。接着枚举没有被并入到 MST 的边 (u,v)（我们将把这条边加入到 MST 中，并在原 MST 中删去一条最大边，使新 ST 仍然联通），权值为 $W_e$。查询树上 u ->v 的路径，在路径选取一个边权最大值 $W_m$。则当前枚举的答案为 $W-W_m+W_e$。枚举所有的边之后，取最小值即可。

基本无需证明。这个代码就不给了，可以用倍增和树剖等实现。

接下来讲解严格次小生成树的做法。

原方法是枚举一条边 $W_e$，之后再寻找一条 MST 上的合法最大边（即在路径上）$W_m$。显然 $W_e \geq W_m$，因此可能由此得到的次小生成树并非严格。所以我们可以再查找路径上的严格次小值 $W_{m2}$，则显然 $W_e > W_{m2}$，所以由此得到的生成树一定严格小于 MST。同样枚举所有的边，取最小值即可。

顺便一提，我这题错的地方忘记加了这个，跳点的倍增数组：

gup[i][j]=gup[gup[i][j-1]][j-1];

MMP

以及，两种算法的时间复杂度皆为：$O(m\ logn)$

补充：合并严格最大值和次大值

假设合并的两对最大值 / 次大值分别为 $m_1,s_1,m_2,s_2$，新的最大值 / 次大值为 $m,s$。

我们可以证明，$m$ 一定会在 $m_1,m_2$ 决出，则直接在两个里取个最大值就行。

然后 $s$ 首先在 $s_1,s_2$ 取最大值，若 $m_1$ 不等于 $m_2$，再与 $min(m_1,m_2)$ 进行比对。

Code

// Code by ajcxsu
// Problem: Second Minium Spanning Tree

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+10, M=3e6+10;
struct Edge {
    int u,v;
    ll w;
    bool operator < (const Edge &b) { return w<b.w; }
} e[M];
bool S[M]; // 标记MST
int h[N],to[M],nexp[M];
ll W[M];
int p=1;
inline void ins(int a, int b, int w) {
    nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++;
}

int fa[N];
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return false;
    fa[af]=bf;
    return true;
}

const int OP=20;
int dep[N], gup[N][OP], ma[N][OP], sma[N][OP];
void dfs(int x, int k) {
    dep[x]=k;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            gup[to[u]][0]=x;
            ma[to[u]][0]=W[u];
            sma[to[u]][0]=-1;
            dfs(to[u], k+1);
        }
}

ll m1,m2;
inline void upd(ll x) {
    if(x>m1) m2=m1, m1=x; // m1的值一定要移到m2
    else if(x<m1 && x>m2) m2=x;
}
void lca(int a,int b) {
    m1=m2=0;
    if(dep[a]<dep[b]) swap(a,b);
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[a][j]]>=dep[b]) upd(ma[a][j]), upd(sma[a][j]), a=gup[a][j];
    if(a==b) return;
    for(int j=OP-1;j>=0;j--)
        if(gup[a][j]!=gup[b][j]) {
            upd(ma[a][j]), upd(sma[a][j]);
            upd(ma[b][j]), upd(sma[b][j]);
            a=gup[a][j], b=gup[b][j];
        }
    int j=0;
    upd(ma[a][j]), upd(sma[a][j]);
    upd(ma[b][j]), upd(sma[b][j]);
}

template <typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    int n,m;
    gn(n), gn(m);
    for(int i=0;i<m;i++)
        gn(e[i].u), gn(e[i].v), gn(e[i].w);
    sort(e,e+m);
    ll mst=0;
    for(int i=0, cnt=0;i<m && cnt!=n-1;i++) {
        if(Union(e[i].u, e[i].v)) {
            S[i]=1, mst+=e[i].w;
            ins(e[i].u, e[i].v, e[i].w), ins(e[i].v, e[i].u, e[i].w);
            cnt++;
        }
    }
    dfs(1,1);
    int a[4],ee,ff;
    for(int j=1;j<OP;j++)
        for(int i=1;i<=n;i++) {
            gup[i][j]=gup[gup[i][j-1]][j-1];
            a[0]=ma[i][j-1], a[1]=ma[gup[i][j-1]][j-1];
            a[2]=sma[i][j-1], a[3]=sma[gup[i][j-1]][j-1];
            ee=max(a[0],a[1]), ff=max(a[2],a[3]);
            if(a[0]!=a[1]) ff=max(ff, min(a[0],a[1]));
            ma[i][j]=ee, sma[i][j]=ff;
        }

    ll ans=0x7ffffffffffffll;
    for(int i=0;i<m;i++)
        if(!S[i]) {
            lca(e[i].u, e[i].v);
            if(m1!=e[i].w) ans=min(ans, -m1+e[i].w);
            else ans=min(ans, -m2+e[i].w);
        }
    printf("%lld\n",mst+ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/smst-problem.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆