企业官网建设流程全解析

某大厂OD机试的双机位C卷里，有一道题叫《Alice的安全旅行》。考场上不少同学一看到“旅行”两个字，第一反应就是深搜、广搜、回溯，结果样例过了、数据一大就超时，出来直拍大腿。这道题表面上是“从A到B找一条路”，本质上考的是图论里的瓶颈路径，和“旅行”本身没太大关系。本篇文章我用C++把这道题从头到尾讲透，包括题目建模、并查集离线做法、二分答案做法、最大生成树+LCA的高级扩展，以及机试实战中容易忽略的边界坑，给准备OD机试C卷的朋友一份可以直接照着写的参考。

1. 题目还原：Alice的安全旅行到底在求什么

1.1 题目故事

原题给了一个很友好的包装：某个地图上一共有n个城市，m条双向连接的道路，每条道路上有一个安全评分。Alice从城市s出发，要到城市t去旅行。她希望整条路尽量安全，于是定义：一条路径的安全程度，等于这条路径上所有道路安全评分里的最小值。

换句话说，走一条路就像一根链条，最脆弱的那一环决定了整条链的强度。Alice想知道，在所有从s到t的路径中，这个“最小值”最大能是多少。

翻译成图论语言就是：给定一个无向带权图，求从s到t的所有路径中，路径上最小边权的最大值。这类问题在算法界有个专门的名字：最大瓶颈路径问题（Maximum Bottleneck Path Problem）。

很多同学看到这题的第一反应是“最短路”，然后自然地想写Dijkstra或者SPFA，把距离累加改成取最小值。这个思路方向是对的，但如果没有理解“瓶颈”的含义，很容易在状态更新时写错。

1.2 样例模拟：徒手算一遍

假设题目给了下面这组数据：

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

这里n=5个城市，m=6条边，起点是1，终点是5。我们来手动枚举一下从1到5的几条路径：

• 1 → 2 → 5：安全评分分别是3和4，整条路径的安全值是 min(3, 4) = 3
• 1 → 2 → 3 → 5：安全值 min(3, 5, 1) = 1
• 1 → 4 → 5：安全值 min(1, 2) = 1
• 1 → 2 → 5 → 4 → ？ 这条路绕远了，安全值也不会超过3

所以最终答案是3。Alice会选择走1 → 2 → 5这条路线，虽然它不是距离最短的，但是它的“最差路段”已经是最优的了。

这个例子告诉我们：题目要的不是“路径长度总和最小”，而是“路径上最小安全评分最大”。如果你拿普通最短路的框架去套，把累加改成取min，其实也能跑，但那属于Dijkstra变种，我们后面专门讲。

1.3 数据范围与输出约定

机试真题一般会给到：

• n 最大 10^5，m 最大 2 * 10^5
• 安全评分 w 最大 10^9，因此必须用 long long
• 如果s无法到达t，题目通常要求输出 -1
• 如果s == t，意味着不需要走任何道路，空路径的瓶颈值按 0 处理（具体以考场题目说明为准）

看到10^5级别的点和2*10^5级别的边，纯DFS搜索所有路径就是找死了，别碰。所有设计算法时，时间复杂度至少要控制在 O(m log m) 或者 O((n+m) log W) 这个量级。

2. 从四个角度拆解题思路：为什么这是并查集的题

2.1 暴力思路和它的天花板

最简单的想法是：枚举一个安全阈值x，然后只看安全评分 ≥ x 的那些边，判断s和t是否连通。如果连通，说明存在一条路径，它的每条边都不低于x，那么路径安全值至少为x。然后不断增大x，找到最大的可行x。

这个思路本身是对的，但问题是“怎么找x”。如果从0到最大边权一个一个试，假设最大边权是10^9，那就得跑10^9次连通性判断，每次O(n+m)，绝对超时。

优化方向有两个：

1. 把x的取值二分，把线性枚举变成对数枚举；
2. 把边按权值排序，从大到小一条一条加，加的过程中实时判断连通性。

这两个方向分别对应后面要写的解法二和解法一。

2.2 加边顺序里的单调性

这个题最妙的地方在于单调性。

假设你有一个“只允许走安全评分≥x的边”的规则，那么当x越大的时候，能走的边越少，s和t越难连通；当x越小的时候，能走的边越多，s和t越容易连通。所以“s和t是否连通”这个函数，在x从小到大的过程中只会从“连通”变成“不连通”，不会反复横跳。

利用这个性质，把边按安全评分从大到小排序，然后一条一条加进图里。每次加入一条边，就检查s和t是否已经连通。第一次发现它们连通的那条边，它的权值就是最大瓶颈值。

为什么？因为在加入这条边之前，所有权值比它大的边都不足以让s、t连通，也就是说任何路径只要全部由“更大权值边”组成都到不了t。而加入这条边之后，s、t连通了，说明存在一条路径，路径上所有边的权值都 ≥ 当前这条边的权值。路径的瓶颈值就是当前这条边的权值，而且这个瓶颈值已经是能取到的最大可能值了。

这种“按边权排序后不断加边”的思路，其实就是Kruskal最小生成树算法的核心框架。所以这道题用并查集解，本质上不是生搬硬套，而是看到了问题结构里的单调性。

2.3 另一种思路：答案的可二分性

有了上面的单调性，二分答案也就顺理成章了。

对答案x做二分。check(x)的时候，遍历所有边，只把安全评分 ≥ x 的边加入一个临时图，然后BFS或DFS判断s和t是否连通。如果连通，说明答案至少是x，可以尝试更大的值；如果不连通，说明x太大，要把上界往下压。

二分次数大约是 log2(10^9) ≈ 30次。每次check遍历一遍全图，复杂度O(n+m)。总共约30 * 3*10^5 = 10^7级别操作，在2秒的时间限制内完全可以跑完。

这个方法有个额外好处：代码不需要排序，也不需要并查集，只需要邻接表和BFS。对于本来就会写BFS的同学来说，这个方案最亲切，也最不容易写错数据结构。

2.4 Dijkstra变种：把瓶颈值当成距离

还有一个思路也值得说，因为它能帮你加深对这个题的理解。

定义 dist[u] 为：从s到u的所有路径中，最大瓶颈值。那么初始时 dist[s] = ∞，其余为 -1。当我们从u走向v时，新路径的瓶颈值是 min(dist[u], w(u, v))。如果这个值比 dist[v] 大，就更新 dist[v]。

这本质上就是Dijkstra算法在“max-min”运算规则下的推广。Dijkstra贪心选当前dist最大的点扩展，依然正确。复杂度O(m log n)。

这解法可以作为思路参考，但我个人不推荐机试首选。因为并查集的代码更短，而且不需要写优先队列。如果你对Dijkstra极其熟练，考试时用它也没问题，但如果你两种都会，我还是建议选并查集，原因见下一节。

2.5 为什么最终首选并查集

对比下来，并查集做法有几个实打实的优势：

• 代码量最小：一个DSU结构体加一个排序就完了，连邻接表都不用建；
• 复杂度最稳：O(m log m)，不受边权范围影响；
• 不容易写错：思路很直白，加边、查连通，逻辑链短；
• 现场调试方便：就算样例不过，print一下“当前加到的边”和“s、t各自根节点”就能快速定位问题。

二分+BFS的优势在于“BFS模板更通用”，但每次check都要重新初始化visited数组，还要小心递归爆栈的问题。并查集完全没这些事。而且这道题只需要回答一次查询，如果题目变成多组查询，并查集离线还能配合可撤销并查集处理，扩展性也很强。

3. C++ 实现：并查集与二分版源码级讲解

3.1 离线并查集版（推荐AC代码）

直接给完整代码。环境以C++17为准，考场一般支持#include <bits/stdc++.h>，如果不支持就手动补头文件。

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v; long long w; }; struct DSU { vector<int> fa, sz; DSU(int n) : fa(n + 1), sz(n + 1, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; // 路径压缩，写成递归也可以 x = fa[x]; } return x; } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); fa[b] = a; sz[a] += sz[b]; return true; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin >> n >> m >> s >> t; vector<Edge> edges; edges.reserve(m); for (int i = 0; i < m; i++) { int u, v; long long w; cin >> u >> v >> w; edges.push_back({u, v, w}); } if (s == t) { cout << 0 << "\n"; return 0; } sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w > b.w; }); DSU dsu(n); for (const Edge& e : edges) { dsu.unite(e.u, e.v); if (dsu.find(s) == dsu.find(t)) { cout << e.w << "\n"; return 0; } } cout << -1 << "\n"; return 0; }

这个版本已经可以直接跑样例。注意我在find里用的是循环加路径压缩，不是递归。为什么这么做？因为在某些链状的极端数据下，递归find的深度可能会达到O(n)，虽然按秩合并能缓解，但循环版本永远不会爆栈，考试环境里更稳。

3.2 代码关键细节逐行说

有几个点值得展开讲。

第一，排序必须用降序。如果用了升序，你加边的时候是从小到大，s和t第一次连通时，穿过的那条边的权值就是“最小瓶颈路径”里的最小可能值，而不是最大瓶颈值。这个顺序一旦反了，整个算法就错了。

第二，每次都要判断find(s) == find(t)，不一定要unite成功才判断。有人会写成“只有unite返回true才判断”，这在某些情况下会漏答案。比如当前加入的边权值大，但它连接的两个点之前已经通过其它边连通了，此时unite返回false，可是s和t可能因为这条回路变得更连通了吗？其实不会。但为了逻辑统一，更稳妥的写法是加完边后无条件检查一次连通性，反正find是O(α(n))，代价可以忽略。

第三，输出的是当前边的权值，不一定是路径上其他边的权值。因为排序保证之前加入的所有边权值都不小于当前边，所以当前边的权值就是整条路径的最小值。

第四，如果循环结束都没有使s、t连通，说明原图本身就不连通，输出-1。

3.3 二分+BFS版：适合临场改造的备胎

如果你在考场上一时想不到并查集，二分+BFS是很可靠的后备方案。

#include <bits/stdc++.h> using namespace std; int n, m, s, t; vector<vector<pair<int, long long>>> graph; bool check(long long limit) { vector<char> visited(n + 1, 0); queue<int> q; q.push(s); visited[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); if (u == t) return true; for (auto& [v, w] : graph[u]) { if (!visited[v] && w >= limit) { visited[v] = 1; q.push(v); } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> s >> t; graph.assign(n + 1, {}); long long maxWeight = 0; for (int i = 0; i < m; i++) { int u, v; long long w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); maxWeight = max(maxWeight, w); } if (s == t) { cout << 0 << "\n"; return 0; } // 先判断原图是否连通 if (!check(0)) { cout << -1 << "\n"; return 0; } long long left = 0, right = maxWeight; while (left < right) { long long mid = (left + right + 1) / 2; if (check(mid)) { left = mid; } else { right = mid - 1; } } cout << left << "\n"; return 0; }

这套代码的check(0)很妙。因为limit = 0时所有边都满足w >= 0，BFS等价于在原始图上判断连通性，正好用来处理无解的情况，省得单独写一个DFS。

二分的时候用(left + right + 1) / 2，配合left = mid和right = mid - 1，这是为了取上中位数，避免陷入死循环。这个二分模板和普通二分不一样，如果你习惯写mid = (left + right) / 2，就会在left=right-1时永远无法收敛。这一点务必注意。

3.4 更大的框架：如果考多次询问怎么办

上面两个版本都只处理了单次询问。如果题目再升级，变成q组询问（比如q次给出不同的s、t），每次都重新排序或者二分，总复杂度就可能爆掉。

遇到这种情况，正确做法是：

1. 先用Kruskal求一遍最大生成树；
2. 对于任意两点s、t，它们在最大生成树上的唯一路径，就是原图中的最大瓶颈路径；
3. 用树上倍增法维护“路径上的最小边权”，一次查询O(log n)。

这个结论叫做“最小瓶颈路性质”：在无向图中，任意两点的最大瓶颈路径，一定包含在任意一棵最大生成树中。证明思路也不难：如果一条非树边能提供更大的瓶颈值，那么Kruskal构建最大生成树时，它就应该被选进树里，否则会矛盾。

因为本题是单询问，我不建议在机试里写这个加强版，代码量直接翻倍。但如果你平时练题比较多，最好把这套模板背下来，因为“最大生成树+LCA”这个组合在OD机试的较高难度题目里并不罕见。

4. 完整测试用例与边界情况：机试不白给

4.1 手动测试用例

再给几个用例，方便你验证自己的代码。

用例1：普通连通

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

期望输出：3。

用例2：起点终点相同

3 2 2 2 1 2 10 2 3 7

期望输出：0。因为不需要走任何路。

用例3：不可达

4 2 1 4 1 2 5 2 3 4

期望输出：-1。

用例4：只有一条直接边

2 1 1 2 1 2 1000000000

期望输出：1000000000。

用例5：重边

3 3 1 3 1 2 5 1 2 8 2 3 9

期望输出：8。注意第一条1→2权为5，第二条1→2权为8，排序后8这条边让1、2先连通，但此时3还没连上；接着加入9的边2→3，1和3连通，瓶颈是8。不能误以为答案应该是5。

这几个用例覆盖了主要分支。写完代码后，建议先用它们自测，比直接对着大数据调试更有效。

4.2 边界场景清单

除了上面的用例，机试里还要防住这些边界：

• n = 1：只有1个城市，且s和t相同，输出0；
• m = 0：没有任何道路，如果s != t，输出-1；
• 边权为0：如果某些道路安全评分是0，那么sort降序时它们排最后。算法依然正确，但二分版本要注意check(0)返回true不代表答案可以是0，这只是连通性判断；
• 大边权：安全评分达到10^9，用int会溢出，必须long long；
• 自环：u == v的边，并查集unite时会返回false，不影响正确性，可以忽略。

其中最容易翻车的是s == t。很多同学默认答案应该是正无穷，但机试标准输出通常是0。考试时如果题目描述没说，建议按0输出，同时题目一般会保证s和t不同，否则就只能看说明。

4.3 自己构造大数据压测的方法

机试环境通常2秒，如果对自己的复杂度没底，可以自己写个脚本生成极限数据压测。

生成规则很简单：n取100000，m取200000，点编号随机，边权随机取1到10^9。然后用time命令运行程序，看耗时和内存。并查集版本在这种数据下一般能稳定在0.3秒以内，二分+BFS版本大约1秒左右，都在安全线内。

如果你发现自己的程序跑得很慢，先看是不是下面几个问题：

• 没有开ios::sync_with_stdio(false)，导致cin、cout频繁刷新；
• 排序用了结构体拷贝而不是引用；
• BFS的visited数组每次check都重新fill，没有用时间戳优化；
• 递归DFS在链状图上爆栈，导致程序崩溃而不是正常超时。

这些坑我都在模拟赛里踩过，真的耽误时间。

5. 实战复盘：我踩过的坑和机考小技巧

5.1 读题的三个坑

第一，别被故事包装带偏。题目叫“Alice的安全旅行”，核心却是并查集。如果你从“旅行路线”这个角度去联想搜索算法，就会进入误区。机试里的题目名和故事都是障眼法，重点永远是背后的数据结构。

第二，注意安全评分的定义方向。有些题目说的是“危险值越低越安全”，然后让你求最小化最大危险值。那和本题正好相反，需要把排序方向改一下，或者把权重取负。读题时第一件事就是把“越大越好”还是“越小越好”圈出来。

第三，确认路径安全值是“最小值”还是“乘积”。有些变形题会定义路径安全值为所有边权的最小值，有些会定义成乘积，还有定义成和的，完全是三种做法。本题是min，别默认成累加。

5.2 代码层面的坑

并查集版本看起来简单，但如果平时不常写，考场上有几个细节容易出问题：

• iota(fa.begin(), fa.end(), 0)是从0开始填充，所以fa[0] = 0，fa[1] = 1，正好对应1-based节点编号；
• 如果城市编号从0开始，那么DSU初始化要改成DSU(n)，同时fa[i] = i也能覆盖0号点。这种从0还是从1开始的细节，必须看样例的输入数据；
• 比较s和t的根节点时，最好取临时变量，避免多次find造成不必要的开销。

二分+BFS版本也有个隐蔽的坑：graph.assign(n + 1, {})之后，给每个节点push_back边对，内存使用大约是2 * 2 * 10^5 * 16字节，约6MB，没问题。但如果你再开一个同样规模的map而不是vector，内存和常数都会爆炸，别用map存图。

另外，双机位监考模式下，你不能翻书查模板。所以DSU结构体、BFS模板、二分模板这三样东西，平时一定要练到闭着眼睛都能写出来。建议在准备阶段把常用模板默写三遍以上，特别是路径压缩写法，考场上一紧张很容易把fa[x] = find(fa[x])写成fa[x] = find(x)，那就完全错了。

5.3 如何从这道题迁移到其他真题

这道题做题价值很高，因为它衍生出了整整一族的题型：

• 最小化路径最大边权：和本题对称，升序加边或二分条件反过来；
• 多次询问s、t：最大生成树 + LCA，一次预处理O(m log m)，每次询问O(log n)；
• 边权是二维坐标距离：先算边权再套同样框架；
• 点权瓶颈：把点权拆到入边或出边，或者把每个点拆成入点和出点，中间用点权作为边权。

所以我的建议是：这道题不要只背解法，要把“瓶颈路径”这个概念吃透。你会发现很多真题，换了一件“矿山救人”“网络布线”“物流运输”的外衣，内核还是单调性加并查集。

从个人实际经验来看，OD机试C卷里这种“故事包装+经典数据结构”的组合出现频率非常高。看似新颖，实际都是老熟人。准备时与其背诵大量偏题怪题，不如把并查集、二分答案、最小生成树、LCA这四个基础模块练到条件反射。碰到再花哨的旅行故事，都能一眼看穿它究竟在问什么。