企业官网建设流程全解析

凡是认真刷过OD机试图论题的人，看到【Alice的安全旅行】这个名字，多半会心一笑。题目包装得再温馨，内核依旧是最经典的“最小瓶颈路”问题。我拿到2026双机位C卷的时候，这道题排在中后段，一眼看过去以为又是普通最短路，真上手才发现，如果按惯性思维写Dijkstra求边权和，答案会错得很离谱。

这道题特别适合用来练“题目模型翻译”能力：它把图论里非常成熟的“让路径上的最大边权最小”抽象成旅行安全场景。无论你最终是否会遇到原题，把它彻底吃透，以后看到“降低最大风险”“限制单次消耗”“控制最大跳数”这类描述，基本上都是同一套打法。这篇文章我会把题意、三种解法、完整C++代码、考场踩坑经验一次性讲清楚。

1. 题目到底在说什么：从故事到模型的翻译

1.1 题意速览

原题讲的是旅行者在城市间移动的事情，大意可以还原成下面这个模型：

Alice生活的国家有N座城市，编号从1到N，城市之间一共有M条双向道路。每条道路有一个危险等级w，w越大代表这条路越危险。Alice从城市1出发，想去城市N。她只关心一件事：整条路线里最危险的那一段不要超出自己的承受范围。现在要帮她求出这个“最小的最大危险等级”是多少。如果城市1和城市N之间根本没有任何通路，输出-1。

输入格式很直接：

• 第一行两个整数 N、M
• 接下来 M 行，每行三个整数 u、v、w，表示 u 和 v 之间存在一条危险等级为 w 的双向道路

输出一个整数，就是所有从1到N的路径中，每条路径上最大边权的最小值。

数据范围通常是 N、M 都能到 10^5，w 可以到 10^9 量级。所以别指望用 O(N^2) 的朴素算法，必须往 O((N+M)logW) 或者 O(MlogM) 这个方向想。

1.2 这道题为什么不能直接套最短路径

很多人拿到题的第一反应是“求最短路径”，因为平时练得最多的就是Dijkstra及其各种变体。但注意，这里不是求路径上的边权之和，而是求路径上所有边权中的最大值最小。

用一个只有三个城市的例子就能看出差别：

• 道路1：城市1到城市2，危险等级 100
• 道路2：城市2到城市3，危险等级 100
• 道路3：城市1到城市3，危险等级 150

从1到3有两条路：

• 路径A：1 → 2 → 3，边权和 = 200，最大边权 = 100
• 路径B：1 → 3，边权和 = 150，最大边权 = 150

如果按普通最短路去写，Dijkstra会认为路径B更优，因为总和150小于200，输出150。但题目真正问的是“最大危险等级最小”，路径A虽然绕路，但全程最危险的一段只有100，明显更符合Alice的需求，正确答案应该是100。

这就是这类题最阴险的地方：场景包装让你以为要算“总危险度”，实际考的是“瓶颈最小化”。理解错模型，代码写得再漂亮也是白搭。

1.3 难度评估与考点定位

这道题在机试体系里属于200分档，通常放在第三题或第四题的位置。它考的并不只是某一个模板，而是三件事的组合：

1. 能否把故事描述抽象成图模型
2. 是否理解“最小值最大/最大值最小”问题的常规解法——二分答案
3. 是否掌握图连通性验证、并查集、最短路变种等基础算法

从考场表现看，这道题的迷惑性很强。能一眼看出是“最小瓶颈路”的选手，基本十分钟能写完；被名字带偏去写普通最短路的，往往要绕一个大弯才意识到问题。真正考试的时候，如果发现样例能过但总觉得哪里不对劲，就要回头重新读题，看看是不是把“最大边权最小化”理解成了“边权和最小化”。

2. 三种主流解法：谁最稳，谁最优，谁最短

2.1 解法一：二分答案 + BFS/DFS 验证

遇到“最小化最大值”或者“最大化最小值”，第一反应就应该是二分答案，这是考场上最稳、最不容易出错的打法。

为什么能二分？关键在于单调性。假设我们给Alice设置一个可承受的最大危险等级 limit，那么她走的路只能由危险等级不超过 limit 的道路组成。limit 越大，可选的道路就越多，从城市1到达城市N的可能性只增不减；limit 越小，可选的道路就越少，能走通的可能性只减不增。这种“随着limit增大，可行性单调变化”的性质，正是二分答案的前提。

具体流程是这样：

• 二分下界 l 设为0，上界 r 设为所有边中最大的危险等级
• 每次取 mid = (l + r) / 2
• 调用 check(mid) 判断：只用危险等级不超过 mid 的边，能否从1走到N
• 如果能走通，说明答案不高于 mid，记录 ans = mid，然后把 r 缩小到 mid - 1
• 如果走不通，说明 mid 还不够大，把 l 增大到 mid + 1
• 最后如果没有记录到任何 ans，说明不连通，输出-1

check 函数非常好写。建好图之后，从节点1做一次 BFS 或者 DFS，只访问那些边权不大于 mid 的邻居，看能不能碰到节点N就行。这里不涉及最短步数、不涉及权重累加，只关心连通性，所以队列做 BFS 完全够用。

复杂度也很好看：每次 check 是 O(N+M)，二分的次数大约是 O(log W)，W是边权值域。整体 O((N+M)logW)，对于 10^5 量级的输入毫无压力。

2.2 解法二：并查集 + 边权排序

第二种思路在竞赛圈叫“Kruskal 式加边”，乍一看和最小生成树关系很大，实际上只是借用了并查集维护连通分量的能力。

做法如下：把所有边按照危险等级从小到大排序，然后一条一条地加入图中。这里我们不需要真的建图，只需要维护一个并查集，每次把当前边的两个端点合并。每加完一条边，就检查一下节点1和节点N是否已经在同一个集合里。一旦它们连通了，当前这条边的危险等级就是答案。

为什么这个贪心是对的？因为我们是按边权递增的顺序加边的。假设加到某条边的时候，1和N第一次连通了，说明在此之前，所有比这条边权更小的边组成的子图里，1和N是不连通的。也就是说，任何从1到N的路径，都必须至少包含一条权值不小于当前边权的边。既然如此，最小可能的最大边权，恰好就是当前这条边的权值。这个证明可以自己在纸上画一画，会比任何解释都有说服力。

复杂度方面，排序是 O(MlogM)，并查集的操作近似 O(M)，整体就是 O(MlogM)。如果内存和时限允许，这个写法在思路上最清爽，代码量也比二分+BFS少一些，核对起来很舒服。

2.3 解法三：Dijkstra 变形求瓶颈

第三种写法代码量最短，但需要你对Dijkstra的原理有比较透彻的理解。

普通Dijkstra维护的是“到达某个点的路径权值和的最小值”，转移时用 dis[u] + w 去更新 dis[v]。这里我们改一下维护目标：dis[u] 表示“到达城市u的所有路径中，路径上最大边权的最小值”。转移时不再是加法，而是用 max(dis[u], w) 去更新 dis[v]。其他部分完全照搬Dijkstra：优先队列小顶堆，每次弹出当前 dis 最小的节点去松弛邻居。

正确性的直觉可以这样理解：假设已经知道从1到u的最优瓶颈是 dis[u] 这么大，那么从1经过u再走一条边权为w的边到v，整条路径的瓶颈就是 max(dis[u], w)。如果这个值比目前已知的 dis[v] 更小，就说明找到了一条更优的到达v的路线，应该更新掉。用优先队列保证先处理的是瓶颈值最小的节点，后续松弛一定不会比之前的更差，这正是Dijkstra框架适用的条件。

复杂度是 O(MlogN)，和普通Dijkstra完全一致。这个写法最精简，但是对“为什么可以这样做”的理解要求比较高，如果只是套模板，很难想到要把加号换成max。

3. C++ 实现全解析

3.1 二分+BFS版本的完整可提交代码

三种解法中，我最推荐考场上写二分+BFS，因为思路直白、不易写错、边界清楚。下面是一份可以直接提交的C++实现：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<pair<int, int>> g[MAXN]; int n, m; bool check(int limit) { vector<char> vis(n + 1, 0); queue<int> q; q.push(1); vis[1] = 1; while (!q.empty()) { int u = q.front(); q.pop(); if (u == n) return true; for (auto e : g[u]) { int v = e.first; int w = e.second; if (!vis[v] && w <= limit) { vis[v] = 1; q.push(v); } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; int maxw = 0; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); maxw = max(maxw, w); } int l = 0, r = maxw; int ans = -1; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } cout << ans << "\n"; return 0; }

如果你确定考场的编译器支持C++17，for (auto &[v, w] : g[u])这种结构化绑定的写法会更简洁。但说实话，现场跑题的时候我不太建议冒险，用pair的first和second是最保险的，兼容所有常见环境。

3.2 关键代码动作逐个拆解

建图部分要注意无向边必须加两条。很多人只会写g[u].push_back({v, w})，忘掉g[v].push_back({u, w})，结果样例运气好能过，换一组数据直接白给。每一对输入的 u、v、w，都要对称存储。这是图论题的老坑，每次都得提醒自己。

二分边界也有讲究。下界 l 我从0开始，因为边权都是正数，0不会是一个真正可行的上限值，但作为二分起点完全没问题。上界 r 直接取所有边权中的最大值，因为任何一条路径的瓶颈都不可能超过整张图的最大边权。如果你图省事把 r 设成一个很大的常数，比如 10^9，也不是不行，但会白白增加几次 check 调用，稍微有点浪费。

check 函数里，vis数组的作用是防止节点重复入队。这里的 vis 是一个 char 数组而不是 bool 数组，纯粹是为了省一点内存，也可以写成 bool。BFS 一旦在队列中碰到节点 N 就立刻返回 true，因为题目只问连通性，不要求最短路径，所以不用统计步数，也不需要等整层扩展完。

二分的循环条件是l <= r，每次 check 成功时记录 ans 并把右边界收缩；失败时把左边界抬高。循环结束后如果 ans 仍然是 -1，说明在任何 limit 下都不连通，输出 -1 即可。

3.3 多组测试用例实测

拿几组数据实测一下这段代码，顺便演示推理过程。

第一组样例：

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

图中两条路径：1→2→3→4 的最大边权是 max(5,3,2)=5，1→4 直连的最大边权是 8。最优答案是 5。二分过程会先尝试 mid=4，此时 5、3、2 三条边都不超过4，但节点2到节点3的边权为3、节点3到节点4的边权为2，整体能走到4吗？路线1→2需要边权5，超过4，走不通，所以 check(4) 返回 false。接着尝试 mid=5，所有边都能走，check(5) 返回 true，答案记录为5，继续尝试更小的值也没能成功，最终输出5。

第二组样例：

3 1 1 2 5

只有一条连接1和2的边，节点3孤立。无论 limit 多大，BFS 都到不了3，二分过程中 check 永远返回 false，ans 保持 -1，输出 -1。这个用例验证的是不可达场景。

第三组样例：

5 5 1 2 9 2 5 9 1 3 4 3 4 4 4 5 4

1→2→5 的瓶颈是9，1→3→4→5 的瓶颈是4，所以答案4。二分时先用 mid 像4这样的值，1→3→4→5 刚好全通，check 成功，记录4，之后尝试更小值如3或2时，1无法连接到任何节点，失败，最终输出4。

这三组用例覆盖了普通连通、不可达、多路径绕行三种常见情况，实测代码输出都正确。

4. 实战中踩过的坑与调试心得

4.1 六个容易翻车的细节

第一个坑就是无向图只建单向边。我见过太多人栽在这里，尤其样例比较巧的时候，漏一条反向边照样能过。所有图论题，只要题目说“双向道路”“无向图”，建图时就必须双向添加。写完代码后第一时间检查g[u].push_back后面是不是跟着g[v].push_back。

第二个坑是二分上界没取好。有些人习惯把 r 定义成 1e9，然后 mid 也会很大，check 次数太多，虽然不至于超时，但代码看起来不够严谨。正确的做法是读边的时候维护 maxw，直接把右边界设为 maxw。如果题目里 w 可能高达 10^9，用 int 也放得下，但保险起见建议直接用 long long 存 w 和 mid。

第三个坑是 BFS 没有标记访问就入队。这会导致同一个节点反复入队，轻则多刷很多无效遍历，重则在特殊图上跑不出来。只要 vis 数组存在，就一定要在q.push(v)之前把vis[v]置为1，而不是等出队时再标记。这个细节很多初学者会漏。

第四个坑是 check 的提前返回。BFS 一旦遇到目标节点就返回 true，这是没问题的。但要注意，如果题目要求输出完整路径，就不能在发现目标时直接返回，还需要保存前驱节点。这道题只问答案值，所以简化版没问题。如果你在变式题里遇到输出路径的要求，千万别直接搬这段代码。

第五个坑是优先队列的小顶堆写法。Dijkstra变形解法里，如果直接写priority_queue<pair<int,int>> pq，默认是最大堆，弹出的永远是瓶颈值最大的节点，答案会完全错误。必须写成priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq。这个greater太容易被忘。

第六个坑是读入性能。当 M 达到 10^5 甚至更高，cin默认的同步模式会让输入变慢。解决办法就是ios::sync_with_stdio(false); cin.tie(nullptr);放在 main 函数最前面。如果这行没写，某些评测机上会超时。

4.2 大数据范围下的性能与内存

这类题的数据量在 10^5 附近时，二分+BFS的时间在零点几秒到一秒出头之间，非常稳。BFS每次都要开新的 vis 数组，size为 N+1，10^5级别的数组开一次就是一两百KB，二分20次也就几MB，内存完全没问题。并查集解法则更省，只需要 parent 数组和排序后的边数组，内存占用最小。

有人说二分+BFS比并查集多一个 logW 因子，会不会更慢？实测中不会。因为 W 即便到 10^9，logW 也就30左右，每次 BFS 都是 O(N+M)，总操作量在 3×10^6 量级，现代评测机一两秒稳稳跑完。担心性能的话，优先用并查集，排序一次然后线性加边，是最少的操作次数。

4.3 考场时间分配与答题策略

双机位监考的模式下，代码很难反复调试，所以思路不清晰之前别急着敲键盘。我给自己定的规矩是：看到“最小化最大/最大化最小”的题，先花三分钟在草稿纸上确认有没有单调性；确认有，再开始写二分答案。如果确认不是二分，再考虑是不是Dijkstra变形、并查集、BFS状态搜索。

这道题留25到35分钟比较合理。前10分钟用来读题、建模型、确认输出要求；10到20分钟写代码并跑样例；剩下的时间构造边界数据自测。边界数据至少要包括：单节点图、两个节点直接相连的图、不可达的图、全图边权相等的图。每一组都要想清楚预期输出是多少，再拿程序跑一遍。

5. 一些题外话：这道题教会我的东西

我自己做这道题最大的收获，不是记住了什么模板，而是意识到机试真正考察的是“把自然语言翻译成数学模型”的能力。Alice的安全旅行说得再生动，本质就是一张有权无向图上的瓶颈最小化问题。一旦完成这个翻译，接下来选二分还是并查集，只是个人偏好的问题。

另外有一点值得提醒：做完这道题后，可以顺手把变式也想一遍。如果题目改成“路径上边权总和最小但路径长度不能超过K”，那就是分层图加最短路径；如果改成“必须经过若干个检查站”，那就变成多段最短路的组合问题。机试题目之间联系很紧密，吃透一题，往往能顺带拿下三五道变种。

如果你正准备这类考试，建议把二分答案、并查集、Dijkstra变形这三板斧都练熟，遇到类似名字的题目先笑一笑，然后冷静分析它到底考什么模型。做题的心态稳住，代码一遍过的概率就会高很多。