「一本通 3.1 练习 3」秘密的牛奶运输

形式化题目

给定一个带权无向连通图 $G = (V, E)$ ， $|V| = n$ ， $|E| = m$ ，每条边 $e = (x, y)$ 有权值 $z$ （可能有重边）。

生成树是包含全部 $n$ 个顶点的无环连通子图，其权值为所选边权之和。求权值严格第二小的生成树的权值，即所有与最小生成树（MST）权值不同、且大于 MST 权值的生成树中权值最小者。

样例：

text

MST 取边 $1\text{-}2\ (100)$ 、 $3\text{-}4\ (100)$ 、 $2\text{-}4\ (200)$ ，权值 $400$ ；严格第二小的生成树把 $2\text{-}4$ 换成 $2\text{-}3$ ，权值 $450$ 。

正解

思路

1. 从「枚举生成树」到「换边」

生成树总数是指数级的，不能枚举。但第二小的生成树离 MST 非常近——它与 MST 至多相差一条边（换边引理）：

把一条非树边 $(u, v)$ 加入 MST，必然形成唯一一个环；删掉环上除 $(u, v)$ 以外的任意一条边，就得到另一棵生成树。而任一生成树与 MST 的差异都可以通过这样的单次换边逼近，因此严格次小生成树必然是「MST + 一条非树边，删环上最大边」的结果。

于是做法分三步：

Kruskal 求出 MST，记录总权 $w_{MST}$ 、树的邻接表、每条原始边是否在树上；
枚举每条非树边 $(u, v, w)$ ：在树上求 $u \to v$ 路径，取路径上的最大边权 $\mathrm{maxw}$ ；
候选权值 $w_{MST} + w - \mathrm{maxw}$ ，在全部候选中取最小。

2. 「第二小」必须严格：过滤等权换边

若 $w = \mathrm{maxw}$ ，换边后权值不变，候选值等于 $w_{MST}$ ——这只是把 MST 换了个形状（等权换边，重边场景很常见），并不是「第二小」。因此枚举时必须加条件 $w > \mathrm{maxw}$ ，只保留严格变大的候选。

这一步是本题唯一的正确性陷阱：真实测试数据里有大量等权重边，第一版代码不过滤时 10 组全部输出 MST 权值（比正确答案小），过滤后 10/10 通过。（ $w < \mathrm{maxw}$ 不可能出现，否则原 MST 不是最小的，矛盾。）

3. 样例推演

下图是样例的 MST（实线）与唯一非树边（虚线）：

flowchart LR
    n1["1"] ---|"100"| n2["2"]
    n4["4"] ---|"200"| n2
    n4 ---|"100"| n3["3"]
    n2 -.-|"250"| n3

非树边 $2\text{-}3$ 加入后形成环 $2\text{-}4\text{-}3$ ，环上最大边是 $2\text{-}4\ (200) < 250$ ，满足严格条件，候选 $= 400 + 250 - 200 = 450$ ：

候选	非树边 $w$	环上最大边 $\mathrm{maxw}$	$w > \mathrm{maxw}$	候选权值
1	$2\text{-}3\ (250)$	$200$ （边 $2\text{-}4$ ）	是	$400 + 250 - 200 = 450$

答案 $450$ ，与样例输出一致。注意表中若某非树边满足 $w = \mathrm{maxw}$ ，该行必须丢弃。

4. 为什么 $N \leqslant 500$ 可以直接树上 BFS

$L \leqslant 10^5$ 的次小生成树题需要 LCA + 倍增预处理路径最值；本题 $n \leqslant 500$ 、 $m \leqslant 10^4$ ，对每条非树边做一次树上 BFS（记录 parent 再回溯取最大）只要 $O(n)$ ，总计 $O(nm)$ 完全够用，实现也更短。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from collections import deque


def find(fa: list[int], x: int) -> int:
    """并查集查根：路径压缩。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[list[tuple[int, int]]], list[bool]]:
    """Kruskal 求最小生成树：返回 (总权, 邻接表, 每条边是否在树上)。"""
    fa = list(range(n + 1))
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    in_tree = [False] * len(edges)
    total = 0
    for i, (x, y, z) in enumerate(sorted(edges, key=lambda e: e[2])):
        rx, ry = find(fa, x), find(fa, y)
        if rx != ry:
            fa[rx] = ry
            total += z
            in_tree[i] = True
            adj[x].append((y, z))
            adj[y].append((x, z))
    return total, adj, in_tree


def max_on_path(adj: list[list[tuple[int, int]]], u: int, target: int) -> int:
    """树上 BFS 找 u 到 target 的路径，返回该路径上的最大边权。"""
    # parent[v] = (前驱节点, 该段边权)，用于回溯整条路径
    parent: dict[int, tuple[int, int]] = {u: (0, 0)}
    q = deque([u])
    while q:
        cur = q.popleft()
        if cur == target:
            break
        for nxt, w in adj[cur]:
            if nxt not in parent:
                parent[nxt] = (cur, w)
                q.append(nxt)
    # 回溯路径上的所有边权取最大
    best = 0
    cur = target
    while cur != u:
        prev, w = parent[cur]
        best = max(best, w)
        cur = prev
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges = [(next(data), next(data), next(data)) for _ in range(m)]

    mst, adj, in_tree = kruskal(n, edges)

    # 枚举每条非树边 (u,v,z)：替换 MST 中 u-v 路径上的最大边得到候选方案。
    # z 等于路径最大边时候选值 = mst（等权替换），题目要严格第二小，只保留 > mst 的候选。
    ans = min(
        mst + z - max_on_path(adj, x, y)
        for i, (x, y, z) in enumerate(edges)
        if not in_tree[i] and z > max_on_path(adj, x, y)
    )
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:05
 * update_at: 2026-10-05 04:05
 */

// 严格次小生成树（换边法）：
// 1. Kruskal 求出 MST，记录总权 w_mst、树的邻接表、每条原始边是否在树上；
// 2. 枚举每条非树边 (x,y,z)，在树上 BFS 求 x->y 路径上的最大边权 maxw；
// 3. 候选权值 = w_mst + z - maxw，要求 z > maxw（严格第二小，等权换边不算），
//    在全部候选中取最小。
// 本题 n <= 500, m <= 1e4，每条非树边 BFS 一次 O(n)，总 O(nm) 即可，无需倍增 LCA。

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

typedef long long ll;

const int MAXN = 505;
const int MAXM = 10005;

int n, m;
int fa[MAXN]; // Kruskal 并查集

// 边表：同时保存原始输入顺序，tree_edge[] 标记该边是否被 Kruskal 选中
struct Edge {
    int x, y;
    ll z;
};
Edge edges[MAXM];
bool tree_edge[MAXM];

// MST 的邻接表（树题规模小，用 vector 邻接表更直观）
vector<pair<int, ll> > g[MAXN];

// BFS 求树上路径最大边权用的数组
int parent[MAXN];        // BFS 树上的前驱节点，0 表示未访问
ll parent_w[MAXN];       // 前驱边（parent[v] -> v）的边权
int que[MAXN];           // 手写队列

// 并查集查找（路径压缩）。
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

// Kruskal 排序用的比较函数：按下标比较边权。
bool cmp_edge(int a, int b) {
    return edges[a].z < edges[b].z;
}

// Kruskal 求最小生成树，返回 MST 总权值。
ll kruskal() {
    // 按边权从小到大排序；用下标排序，保留原始边编号以便标记 tree_edge
    int order[MAXM];
    for (int i = 1; i <= m; i++) order[i] = i;
    sort(order + 1, order + m + 1, cmp_edge);

    for (int i = 1; i <= n; i++) fa[i] = i;

    ll total = 0;
    int cnt = 0;
    for (int k = 1; k <= m; k++) {
        int i = order[k];
        int rx = find(edges[i].x), ry = find(edges[i].y);
        if (rx == ry) continue;
        fa[rx] = ry;
        total += edges[i].z;
        tree_edge[i] = true;
        cnt++;
        // 建树的邻接表
        g[edges[i].x].push_back(make_pair(edges[i].y, edges[i].z));
        g[edges[i].y].push_back(make_pair(edges[i].x, edges[i].z));
        if (cnt == n - 1) break;
    }
    return total;
}

// 在树上 BFS 求 u 到 target 的路径，返回路径上的最大边权。
// parent[v] 记录前驱，找到 target 后回溯取最大。
ll max_on_path(int u, int target) {
    for (int i = 1; i <= n; i++) parent[i] = 0;
    parent[u] = u;
    int head = 1, tail = 1;
    que[tail] = u;
    while (head <= tail) {
        int cur = que[head];
        head++;
        if (cur == target) break;
        for (int j = 0; j < (int)g[cur].size(); j++) {
            int nxt = g[cur][j].first;
            ll w = g[cur][j].second;
            if (parent[nxt] == 0) {
                parent[nxt] = cur;
                parent_w[nxt] = w;
                tail++;
                que[tail] = nxt;
            }
        }
    }
    // 从 target 沿前驱回溯到 u，取路径上最大边权
    ll best = 0;
    int cur = target;
    while (cur != u) {
        best = max(best, parent_w[cur]);
        cur = parent[cur];
    }
    return best;
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].x >> edges[i].y >> edges[i].z;
    }

    ll mst = kruskal();

    // 枚举每条非树边，换掉环上最大边得到候选生成树。
    // 必须要求 z > maxw：z == maxw 时换边后权值不变（等权换边，重边场景常见），
    // 候选值等于 MST 权值，不是严格第二小。
    ll ans = -1; // -1 表示还没有合法候选
    for (int i = 1; i <= m; i++) {
        if (tree_edge[i]) continue;
        ll maxw = max_on_path(edges[i].x, edges[i].y);
        if (edges[i].z <= maxw) continue;
        ll candidate = mst + edges[i].z - maxw;
        if (ans == -1 || candidate < ans) ans = candidate;
    }

    cout << ans << endl;
    return 0;
}

复杂度

时间复杂度：Kruskal 排序 $O(m \log m)$ ，并查集操作近似 $O(m)$ ；每条非树边一次树上 BFS $O(n)$ ，共 $O(nm)$ 。总计 $O(m \log m + nm)$ ， $n \leqslant 500,\ m \leqslant 10^4$ 时最坏约 $5 \times 10^5$ 量级的内层访问，最大一组实测 0.61 秒（本地验证脚本为 OJ 时限的 20 倍放宽）。
空间复杂度：边表与邻接表 $O(n + m)$ ，BFS 的 parent 字典 $O(n)$ ，实测峰值 18.5MB，远小于 128MB 限制。

总结

严格次小生成树的标准换边法：先 Kruskal 求 MST，再枚举非树边，用「加入非树边形成的环上最大边」作替换对象，候选权值为 $w_{MST} + w - \mathrm{maxw}$ 。「第二小」要求严格大于 MST，所以必须丢弃 $w = \mathrm{maxw}$ 的等权换边——这是重边数据下最容易踩的坑。本题 $n$ 很小，路径最大边权用树上 BFS 现查即可，无需倍增预处理。