我的算法书 - 严格次小生成树

一句话算法

严格次小生成树先求一棵 MST，再枚举每条非树边，尝试替换它在 MST 路径上的最大边或严格次大边。

问题模型

给定一张无向连通带权图，求权值和严格大于最小生成树、且在所有满足条件的生成树中权值最小的一棵生成树。

“严格”表示答案必须满足：

w(T') > w(MST)

如果只得到相同权值的另一棵 MST，不算严格次小生成树。

核心直觉

先固定一棵 MST。任意加入一条非树边 $(u,v,w)$ ，MST 中 $u$ 到 $v$ 的路径会和这条新边形成一个环。

要重新变成生成树，必须从这个环里删掉一条边。为了让新树尽量小，应该删掉路径上能删的最大边。

但严格次小生成树有一个细节：

如果非树边权 $w$ 大于路径最大边，删最大边即可。
如果 $w$ 等于路径最大边，删它只会得到同权 MST，不严格；此时要尝试删路径上小于 $w$ 的最大边，也就是严格次大边。

算法步骤

用 Kruskal 求出一棵 MST，记录 MST 权值和 mst，并标记哪些边被选入 MST。
把 MST 边建成一棵树。
在 MST 树上做倍增预处理：
- up[k][u]：点 u 向上跳 $2^k$ 步到达的祖先；
- mx1[k][u]：这段路径上的最大边权；
- mx2[k][u]：这段路径上严格小于最大值的次大边权。
枚举每条非树边 $(u,v,w)$ ：
- 查询 MST 中 $u$ 到 $v$ 路径上的最大边 largest 和严格次大边 second_largest；
- 若 largest < w，候选答案为 mst + w - largest；
- 否则若 second_largest < w，候选答案为 mst + w - second_largest；
- 否则这条边不能产生严格更大的生成树。
所有候选取最小值。

算法证明

关键结论： 存在一棵严格次小生成树，可以由某棵 MST 只换一条边得到。

加入非树边必成环

MST 是树。向树中加入任意一条非树边 $(u,v)$ ，一定在 $u$ 到 $v$ 的树路径上形成唯一环。
一次换边保持生成树

在这个环中删去任意一条原 MST 边，图重新变成 $n-1$ 条边且连通，因此仍是生成树。
候选树覆盖最优解

设 $T'$ 是一棵严格次小生成树。比较 $T'$ 和 MST，取 $T'$ 中任意一条不在 MST 中的边 $e$ 。把 $e$ 加入 MST 后形成一个环。这个环上至少有一条 MST 边不在 $T'$ 中，删去其中合适的一条可以得到另一棵生成树。

MST 的最小性保证，单次换边得到的增量不会比 $T'$ 的总增量更差。因此枚举所有非树边的单次换边候选，必然能覆盖严格次小生成树的最优答案。
为什么要维护次大边

若非树边权等于路径最大边，删最大边得到的权值仍为 mst，不满足严格大于。此时必须找路径上严格小于它的最大边，才能得到最小的正增量。

所以算法正确。

复杂度分析

Kruskal 排序复杂度为 $O(m\log m)$ 。

倍增预处理复杂度为 $O(n\log n)$ 。

每条非树边查询路径最大/次大边复杂度为 $O(\log n)$ ，总复杂度为：

O(m\log m+m\log n)

空间复杂度为 $O(n\log n+m)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

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

const long long INF = (1LL << 62);
const long long NEG = -(1LL << 60);

struct Edge {
    int u, v;
    long long w;
    int id;
    bool used = false;

    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

struct DSU {
    vector<int> fa;

    explicit DSU(int n = 0) { init(n); }

    void init(int n) {
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
    }

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

    bool merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        fa[a] = b;
        return true;
    }
};

struct StrictSecondMST {
    int n, lg;
    vector<Edge> edges;
    vector<vector<pair<int, long long>>> tree;
    vector<int> depth;
    vector<vector<int>> up;
    vector<vector<long long>> mx1, mx2;

    explicit StrictSecondMST(int n) : n(n) {
        lg = 1;
        while ((1 << lg) <= n) lg++;
        tree.assign(n + 1, {});
        depth.assign(n + 1, 0);
        up.assign(lg, vector<int>(n + 1, 0));
        mx1.assign(lg, vector<long long>(n + 1, NEG));
        mx2.assign(lg, vector<long long>(n + 1, NEG));
    }

    void add_edge(int u, int v, long long w, int id) {
        edges.push_back({u, v, w, id, false});
    }

    void add_value(long long x, long long& a, long long& b) {
        if (x == NEG) return;
        if (x > a) {
            if (x != a) b = a;
            a = x;
        } else if (x < a && x > b) {
            b = x;
        }
    }

    pair<long long, long long> merge_pair(pair<long long, long long> x,
                                          pair<long long, long long> y) {
        long long a = NEG, b = NEG;
        add_value(x.first, a, b);
        add_value(x.second, a, b);
        add_value(y.first, a, b);
        add_value(y.second, a, b);
        return {a, b};
    }

    void dfs(int u, int fa) {
        for (auto [v, w] : tree[u]) {
            if (v == fa) continue;
            depth[v] = depth[u] + 1;
            up[0][v] = u;
            mx1[0][v] = w;
            dfs(v, u);
        }
    }

    void build_lca() {
        depth[1] = 1;
        dfs(1, 0);

        for (int k = 1; k < lg; k++) {
            for (int u = 1; u <= n; u++) {
                int mid = up[k - 1][u];
                up[k][u] = up[k - 1][mid];
                auto merged = merge_pair({mx1[k - 1][u], mx2[k - 1][u]},
                                         {mx1[k - 1][mid], mx2[k - 1][mid]});
                mx1[k][u] = merged.first;
                mx2[k][u] = merged.second;
            }
        }
    }

    pair<long long, long long> path_max_two(int a, int b) {
        pair<long long, long long> ans = {NEG, NEG};

        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];
        for (int k = 0; k < lg; k++) {
            if (diff >> k & 1) {
                ans = merge_pair(ans, {mx1[k][a], mx2[k][a]});
                a = up[k][a];
            }
        }

        if (a == b) return ans;

        for (int k = lg - 1; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                ans = merge_pair(ans, {mx1[k][a], mx2[k][a]});
                ans = merge_pair(ans, {mx1[k][b], mx2[k][b]});
                a = up[k][a];
                b = up[k][b];
            }
        }

        ans = merge_pair(ans, {mx1[0][a], mx2[0][a]});
        ans = merge_pair(ans, {mx1[0][b], mx2[0][b]});
        return ans;
    }

    long long solve() {
        sort(edges.begin(), edges.end());
        DSU dsu(n);

        long long mst = 0;
        int cnt = 0;
        for (auto& e : edges) {
            if (!dsu.merge(e.u, e.v)) continue;
            e.used = true;
            mst += e.w;
            cnt++;
            tree[e.u].push_back({e.v, e.w});
            tree[e.v].push_back({e.u, e.w});
        }

        if (cnt != n - 1) return -1;

        build_lca();

        long long ans = INF;
        for (const auto& e : edges) {
            if (e.used) continue;
            auto [largest, second_largest] = path_max_two(e.u, e.v);

            long long removed = NEG;
            if (largest < e.w) removed = largest;
            else if (second_largest < e.w) removed = second_largest;

            if (removed != NEG) {
                ans = min(ans, mst + e.w - removed);
            }
        }

        return ans == INF ? -1 : ans;
    }
};

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

    int n, m;
    cin >> n >> m;

    StrictSecondMST solver(n);
    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        solver.add_edge(u, v, w, i);
    }

    cout << solver.solve() << '\n';
    return 0;
}

测试用例

输入：

输出：

解释：MST 权值为 3，加入边 1-3(2) 并替换路径上的一条权值 1 的边，得到严格次小生成树权值 4。

应用分类详解

严格次小生成树的本质是“在 MST 基础上求最小正增量”。

一、严格次小生成树模板

典型模式： 题面明确要求严格次小生成树。

识别信号： “严格次小”“权值严格大于 MST”“第二小生成树”。

核心建模： 先求 MST，再枚举非树边做一次换边。

应用场景	经典题目	核心思路
严格次小生成树模板	luogu-P4180	Kruskal + 倍增维护路径最大/次大边

二、MST 敏感性分析

典型模式： 分析替换某条边后生成树权值如何变化。

识别信号： “加入一条边”“删除一条边”“MST 是否唯一”。

核心建模： 非树边加入后只影响一条树上路径；比较路径最大边即可。

应用场景	经典题目	核心思路
MST 唯一性判断	生成树唯一性题	若存在同权替换边，则 MST 不唯一
边权扰动分析	图论构造题	计算每条非树边的换边增量

经典例题

1. luogu-P4180

严格次小生成树模板题。核心难点不是 Kruskal，而是路径查询时必须维护最大边和严格次大边，避免同权替换得到非严格答案。

2. MST 唯一性判断

如果存在一条非树边，其权值等于 MST 路径上的最大边，那么可以做同权替换，说明 MST 不唯一。

3. 生成树边权增量分析

枚举非树边并查询路径最大边，可以得到把这条边强制加入生成树时的最小增量。

参考

Kruskal 最小生成树
倍增 LCA