严格次小生成树

1 问题

设最小生成树的总权值为 WW。严格次小生成树要求:

w(T′)>W, w(T')>W,

并在所有满足这个条件的生成树中,令 w(T′)w(T') 最小。

换成另一棵同权 MST 不算严格次小;原图也可能没有严格次小生成树,例如原图本身就是一棵树,或所有生成树的总权值都相同。

本篇沿用 最小生成树 的 Kruskal 建树,以及 瓶颈路 的树上倍增查询。

2 加边与删边

固定一棵 MST TT。加入一条非树边 e=(u,v,w)e=(u,v,w),会与 TT 中的 uu 到 vv 路径形成唯一环。

要重新得到生成树,必须删去环上的一条原树边 ff。新权值为

W′=W+w−w(f). W'=W+w-w(f).

若要求 W′>WW'>W,就必须满足

w(f)<w. w(f)<w.

为了让新权值尽量小,应删除路径上严格小于 ww 的最大边权。

例如三角形边权为 1,2,21,2,2。MST 取 1,21,2,总权值为 33;加入剩余的 22:

  • 删去原来的 22,仍为 33,只得到另一棵 MST。
  • 删去 11,得到 44,才是严格次小。

同一条非树边换入后,删除同权最大边只得到另一棵 MST,删除严格次大边才能得到四

因此,不能总是删除路径最大边,也不能在非树边等于最大值时直接放弃。

3 单次换边

定理单次换边性质

固定任意一棵 MST,若严格次小生成树存在,则至少有一棵严格次小生成树,可以从这棵 MST 删去一条边、加入一条边得到。

这里说“至少有一棵”,不要求每棵严格次小树都只与固定的 MST 相差一条边。

3.1 证明

设固定 MST 为 TT,任选一棵严格次小树 T∗T^*。记

A=T∗∖T,B=T∖T∗. A=T^*\setminus T,\qquad B=T\setminus T^*.

两边的边数相同。使用一个树的交换引理:可以将 A,BA,B 一一配对为 (ei,fi)(e_i,f_i),使每个 T−fi+eiT-f_i+e_i 都是一棵合法生成树。

由于 TT 最优,每个独立交换的增量都非负:

δi=w(ei)−w(fi)≥0. \delta_i=w(e_i)-w(f_i)\ge0.

又因为配对恰好覆盖所有不同边,

w(T∗)−w(T)=∑iδi>0. w(T^*)-w(T)=\sum_i\delta_i>0.

必有某个 δj>0\delta_j>0,且 δj≤∑iδi\delta_j\le\sum_i\delta_i。因此单次换边得到的树满足

w(T)<w(T−fj+ej)≤w(T∗). w(T)<w(T-f_j+e_j)\le w(T^*).

T∗T^* 已是所有严格大于 MST 的树中最轻的,所以右边只能取等号。单次换边足够。

注意,这些是分别从同一棵 TT 出发的独立交换。证明没有假设把 TT 逐步变成 T∗T^* 时,每一步都只增不减。

交换引理的证明

这部分使用 Hall 匹配定理,可在理解算法后阅读。

先收缩 T,T∗T,T^* 的全部共同边。共同边构成森林,收缩后仍得到同一顶点集上的两棵树,它们的边集分别为 B,AB,A。

构造一个二分图:左侧为 AA 中的边,右侧为 BB 中的边;当 ff 位于 ee 两端在 TT 中的路径上时,连接 e,fe,f。这样的配对正好保证 T−f+eT-f+e 仍是一棵树。

任取左侧边集 X⊆AX\subseteq A,记它的所有右侧邻居为 N(X)N(X)。N(X)N(X) 是树 TT 的边子集,因此是一片森林。每条 XX 中的边,两端都位于这片森林的同一个连通分量,因为它在 TT 中的整条路径都被包含在 N(X)N(X) 中。

一个含 ss 个顶点的分量中,N(X)N(X) 恰有 s−1s-1 条边。而 XX 是另一棵树的边子集,不能成环,所以该分量内部最多容纳 s−1s-1 条 XX 中的边。对所有分量求和,有

∣X∣≤∣N(X)∣. |X|\le |N(X)|.

Hall 定理说明:若左侧任意子集的邻居数都不少于自身,就存在覆盖左侧的匹配。两侧大小相同,这个匹配给出所需的一一配对。

这个引理只要求每对边单独交换后,T−f+eT-f+e 合法;不要求两棵树能够按同一个配对顺序完成交换。

4 最大与严格次大

非树边 e=(u,v,w)e=(u,v,w) 的权值不可能小于树上 u,vu,v 路径的最大边权,否则换掉那条最大边就能让 MST 更轻。

设路径上两个最大的不同边权为 M1,M2M_1,M_2:

  • 若 w>M1w>M_1,删去 M1M_1,候选为 W+w−M1W+w-M_1。
  • 若 w=M1w=M_1,只能删去严格次大值 M2M_2,候选为 W+w−M2W+w-M_2。
  • 若第二种情况中不存在 M2M_2,这条非树边不能产生严格增加的候选。

五、五、三、三、一的路径中,最大值为五,严格次大值为三

例如路径权值为 [5,5,3,3,1][5,5,3,3,1],两个最大不同值是 5,35,3,不是 5,55,5。若新边权为 55,应删 33,增加 22;若新边权为 66,则删 55,增加 11。

5 倍增维护

5.1 信息合并

用 Info{mx1,mx2} 保存两个最大不同值。插入一个候选权值 xx 时:

void add_value(Info &a, ll x) {
    if (x == NEG) return;
    if (x > a.mx1) {
        a.mx2 = a.mx1;
        a.mx1 = x;
    } else if (x < a.mx1 && x > a.mx2) {
        a.mx2 = x;
    }
}

等于最大值的数不能进入第二位。单条边的信息为 {w,NEG},空段为 {NEG,NEG}。

合并两段路径,只需将它们各自的两个候选合并。某个被舍弃的值,在原段内已有两个更大的不同值,因此不可能进入合并后的前两大。

5.2 祖先表与查询

定义:

  • up[u][j]:uu 向上 2j2^j 步的祖先。
  • mx1[u][j]:这段路径的最大边权。
  • mx2[u][j]:这段路径的严格次大边权。

预处理时,合并前后两段 2j−12^{j-1} 路径的信息。查询时,按倍增 LCA 的相同顺序移动两端,将经过的每段信息合入答案。

关键仍是先合并当前段,再移动顶点。两点最后停在 LCA 的两个孩子时,还要补上它们到 LCA 的两条父边。

6 示例

仍用基础篇的五点八边图,固定边集

T={(1,2),(2,3),(3,4),(4,5)},W=10. T=\{(1,2),(2,3),(3,4),(4,5)\},\qquad W=10.

枚举四条非树边:

非树边 路径最大值 M1M_1 严格次大值 M2M_2 删除边权 新权值
(1,3,2)(1,3,2) 22 11 11 1111
(2,4,5)(2,4,5) 44 22 44 1111
(3,5,6)(3,5,6) 44 33 44 1212
(1,5,8)(1,5,8) 44 33 44 1414

第一条非树边等于路径最大值,但仍能删除权值 11 得到合法候选。答案为 1111。

7 代码

采用 luogu P4180: [BJWC2010] 严格次小生成树 的边列表格式。先输入 n,mn,m,再输入 mm 条 u v w,输出严格次小总权值。

原题保证严格次小存在。下面的模板额外约定:原图不连通,或不存在严格次小树时,输出 −1-1。

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

typedef long long ll;
const int maxn = 100000 + 5;
const int maxm = 300000 + 5;

struct Edge {
    int u, v, id;
    ll w;
};

Edge e[maxm];
int fa[maxn], sz[maxn];

void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        sz[i] = 1;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
    return true;
}

bool cmp(const Edge &a, const Edge &b) {
    if (a.w != b.w) return a.w < b.w;
    return a.id < b.id;  // 同权时按输入顺序,便于与正文示例核对
}

const int LOG = 18;
const ll INF = 1LL << 62;
const ll NEG = -(1LL << 62);  // 不存在第二种边权,且小于模板允许的所有边权

struct TreeEdge {
    int to;
    ll w;
};

struct Info {
    ll mx1, mx2;  // 最大值、严格小于最大值的次大值
};

vector<TreeEdge> g[maxn];
bool in_mst[maxm];  // 按原始边编号标记,排序后仍能区分重边
int dep[maxn], up[maxn][LOG], que[maxn];
ll mx1[maxn][LOG], mx2[maxn][LOG];

void add_value(Info &a, ll x) {
    if (x == NEG) return;
    if (x > a.mx1) {
        a.mx2 = a.mx1;
        a.mx1 = x;
    } else if (x < a.mx1 && x > a.mx2) {
        a.mx2 = x;  // 与最大值相等的数不能成为严格次大值
    }
}

Info merge_info(Info a, const Info &b) {
    add_value(a, b.mx1);
    add_value(a, b.mx2);
    return a;
}

Info segment(int u, int j) {
    return {mx1[u][j], mx2[u][j]};
}

bool build_mst(int n, int m, ll &total) {
    init(n);
    for (int u = 1; u <= n; ++u) g[u].clear();
    fill(in_mst, in_mst + m, false);
    sort(e, e + m, cmp);
    total = 0;
    int selected = 0;
    for (int i = 0; i < m && selected < n - 1; ++i) {
        if (!unite(e[i].u, e[i].v)) continue;
        in_mst[e[i].id] = true;
        total += e[i].w;
        ++selected;
        g[e[i].u].push_back({e[i].v, e[i].w});
        g[e[i].v].push_back({e[i].u, e[i].w});
    }
    return selected == n - 1;
}

void build_lifting(int n) {
    for (int u = 0; u <= n; ++u) {
        dep[u] = 0;
        for (int j = 0; j < LOG; ++j) {
            up[u][j] = 0;
            mx1[u][j] = mx2[u][j] = NEG;
        }
    }
    // 用数组队列遍历树,链形 MST 也不会造成递归栈过深。
    int head = 0, tail = 0;
    que[tail++] = 1;
    dep[1] = 1;
    while (head < tail) {
        int u = que[head++];
        for (auto [v, w] : g[u]) {
            if (v == up[u][0]) continue;
            dep[v] = dep[u] + 1;
            up[v][0] = u;
            mx1[v][0] = w;
            for (int j = 1; j < LOG; ++j) {
                int p = up[v][j - 1];
                up[v][j] = up[p][j - 1];
                Info a = merge_info(segment(v, j - 1), segment(p, j - 1));
                mx1[v][j] = a.mx1;
                mx2[v][j] = a.mx2;
            }
            que[tail++] = v;
        }
    }
}

Info path_info(int u, int v) {
    Info answer{NEG, NEG};
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = LOG - 1; j >= 0; --j) {
        if (diff >> j & 1) {
            answer = merge_info(answer, segment(u, j));
            u = up[u][j];
        }
    }
    if (u == v) return answer;
    for (int j = LOG - 1; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            answer = merge_info(answer, segment(u, j));
            answer = merge_info(answer, segment(v, j));
            u = up[u][j];
            v = up[v][j];
        }
    }
    answer = merge_info(answer, segment(u, 0));
    return merge_info(answer, segment(v, 0));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id = i;
    }
    ll total;
    if (!build_mst(n, m, total)) {
        cout << -1 << '\n';
        return 0;
    }
    build_lifting(n);
    ll answer = INF;
    for (int i = 0; i < m; ++i) {
        const Edge &edge = e[i];
        if (in_mst[edge.id] || edge.u == edge.v) continue;
        Info a = path_info(edge.u, edge.v);
        ll removed = NEG;
        if (edge.w > a.mx1) removed = a.mx1;
        else if (edge.w == a.mx1) removed = a.mx2;
        if (removed != NEG) {
            answer = min(answer, total + edge.w - removed);
        }
    }
    // 原题保证严格次小生成树存在;本模板额外约定无解时输出 -1。
    if (answer == INF) cout << -1 << '\n';
    else cout << answer << '\n';
    return 0;
}

使用基础篇的输入:

5 8
1 2 1
2 3 2
1 3 2
3 4 4
2 4 5
4 5 3
3 5 6
1 5 8

输出:

11

模板先用 Kruskal 建 MST,按原始边编号标记是否被选中,再建立树上倍增表。排序后仍使用原编号访问标记,重边也能分别识别。

树的遍历采用数组队列,避免链形 MST 造成递归栈过深。并查集的 find 仍使用路径压缩与按大小合并,树高受到控制。

8 正确性

单次换边性质保证,全部严格次小解中,至少有一个能通过本算法枚举的方式产生。

对固定非树边,加入后形成唯一环;要恢复生成树,只能删除环上的原树边。严格增加要求删边权小于新边权,取其中最大的一个,就得到以这条新边完成交换时的最优候选。

MST 性质保证新边权不小于路径最大值,因此“最大值或严格次大值”覆盖了全部所需情况。倍增查询正确合并路径信息,所有非树边的候选取最小,便得到严格次小权值。

9 复杂度与边界

Kruskal 需要排序与并查集操作,倍增预处理为 O(nlog⁡n)O(n\log n),每条非树边查询 O(log⁡n)O(\log n)。总时间为

O(n+mlog⁡(m+1)+mα(n)+nlog⁡n+mlog⁡n), O\bigl(n+m\log(m+1)+m\alpha(n)+n\log n+m\log n\bigr),

空间为 O(m+nlog⁡n)O(m+n\log n)。

  • 模板支持 n≤105n\le10^5、m≤3×105m\le3\times10^5,LOG=18 覆盖所需层数。
  • 允许零权、负权与重边,本系列按 ∣w∣≤109\lvert w\rvert\le10^9 使用。权值、总和与候选均用 ll。
  • NEG 表示不存在某种边权,INF 表示尚无候选。不能用 00 作为不存在标记。
  • 不存在 MST 用布尔值判断,不能用 total==-1 判断;负权图中 −1-1 也可能是合法总权值。
  • 自环不能成为生成树边,枚举非树边时也要跳过,不能对空路径做换边。
  • 若路径上只有一种边权,严格次大值不存在。不能把另一次出现的最大值放进第二位。
  • 最小生成树不唯一,不代表没有严格次小;但也不能保证一定存在严格次小。例如等权三角形只有同权生成树。

10 练习

10.1 边界数据

分别求下面三张图的 MST 权值与严格次小权值:

  1. 三角形边权 1,2,21,2,2。
  2. 三角形边权 2,2,22,2,2。
  3. 三角形边权 −3,−1,−1-3,-1,-1。
参考结果
  1. MST 为 33,严格次小为 44。
  2. MST 为 44,不存在严格次小。
  3. MST 为 −4-4,严格次小为 −2-2。仍需删除严格次大值,不能使用零初值。

10.2 推荐题目

层次 题目 训练内容
严格次小 luogu P4180: [BJWC2010] 严格次小生成树 完整实现最大、严格次大值的倍增合并,处理自环与同权边。
换边变体 codeforces 609E 对每条边求必须包含它时的最小生成树权值;此题允许结果等于 MST,非树边直接删除路径最大边。点数可达 2×1052\times10^5,需扩大点数组容量。

完成本篇后,可以进一步研究 MST 唯一性与必须包含某条边的最优代价;这些问题都建立在“非树边与树上路径形成环”的关系上。

11 参考

12 相关题解

暂无相关题解