Alice的安全旅行：最小瓶颈路问题全解析

凡是认真刷过OD机试图论题的人看到【Alice的安全旅行】这个名字多半会心一笑。题目包装得再温馨内核依旧是最经典的“最小瓶颈路”问题。我拿到2026双机位C卷的时候这道题排在中后段一眼看过去以为又是普通最短路真上手才发现如果按惯性思维写Dijkstra求边权和答案会错得很离谱。这道题特别适合用来练“题目模型翻译”能力它把图论里非常成熟的“让路径上的最大边权最小”抽象成旅行安全场景。无论你最终是否会遇到原题把它彻底吃透以后看到“降低最大风险”“限制单次消耗”“控制最大跳数”这类描述基本上都是同一套打法。这篇文章我会把题意、三种解法、完整C代码、考场踩坑经验一次性讲清楚。1. 题目到底在说什么从故事到模型的翻译1.1 题意速览原题讲的是旅行者在城市间移动的事情大意可以还原成下面这个模型Alice生活的国家有N座城市编号从1到N城市之间一共有M条双向道路。每条道路有一个危险等级ww越大代表这条路越危险。Alice从城市1出发想去城市N。她只关心一件事整条路线里最危险的那一段不要超出自己的承受范围。现在要帮她求出这个“最小的最大危险等级”是多少。如果城市1和城市N之间根本没有任何通路输出-1。输入格式很直接第一行两个整数 N、M接下来 M 行每行三个整数 u、v、w表示 u 和 v 之间存在一条危险等级为 w 的双向道路输出一个整数就是所有从1到N的路径中每条路径上最大边权的最小值。数据范围通常是 N、M 都能到 10^5w 可以到 10^9 量级。所以别指望用 O(N^2) 的朴素算法必须往 O((NM)logW) 或者 O(MlogM) 这个方向想。1.2 这道题为什么不能直接套最短路径很多人拿到题的第一反应是“求最短路径”因为平时练得最多的就是Dijkstra及其各种变体。但注意这里不是求路径上的边权之和而是求路径上所有边权中的最大值最小。用一个只有三个城市的例子就能看出差别道路1城市1到城市2危险等级 100道路2城市2到城市3危险等级 100道路3城市1到城市3危险等级 150从1到3有两条路路径A1 → 2 → 3边权和 200最大边权 100路径B1 → 3边权和 150最大边权 150如果按普通最短路去写Dijkstra会认为路径B更优因为总和150小于200输出150。但题目真正问的是“最大危险等级最小”路径A虽然绕路但全程最危险的一段只有100明显更符合Alice的需求正确答案应该是100。这就是这类题最阴险的地方场景包装让你以为要算“总危险度”实际考的是“瓶颈最小化”。理解错模型代码写得再漂亮也是白搭。1.3 难度评估与考点定位这道题在机试体系里属于200分档通常放在第三题或第四题的位置。它考的并不只是某一个模板而是三件事的组合能否把故事描述抽象成图模型是否理解“最小值最大/最大值最小”问题的常规解法——二分答案是否掌握图连通性验证、并查集、最短路变种等基础算法从考场表现看这道题的迷惑性很强。能一眼看出是“最小瓶颈路”的选手基本十分钟能写完被名字带偏去写普通最短路的往往要绕一个大弯才意识到问题。真正考试的时候如果发现样例能过但总觉得哪里不对劲就要回头重新读题看看是不是把“最大边权最小化”理解成了“边权和最小化”。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说明不连通输出-1check 函数非常好写。建好图之后从节点1做一次 BFS 或者 DFS只访问那些边权不大于 mid 的邻居看能不能碰到节点N就行。这里不涉及最短步数、不涉及权重累加只关心连通性所以队列做 BFS 完全够用。复杂度也很好看每次 check 是 O(NM)二分的次数大约是 O(log W)W是边权值域。整体 O((NM)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; vectorpairint, int g[MAXN]; int n, m; bool check(int limit) { vectorchar vis(n 1, 0); queueint 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; }如果你确定考场的编译器支持C17for (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)51→4 直连的最大边权是 8。最优答案是 5。二分过程会先尝试 mid4此时 5、3、2 三条边都不超过4但节点2到节点3的边权为3、节点3到节点4的边权为2整体能走到4吗路线1→2需要边权5超过4走不通所以 check(4) 返回 false。接着尝试 mid5所有边都能走check(5) 返回 true答案记录为5继续尝试更小的值也没能成功最终输出5。第二组样例3 1 1 2 5只有一条连接1和2的边节点3孤立。无论 limit 多大BFS 都到不了3二分过程中 check 永远返回 falseans 保持 -1输出 -1。这个用例验证的是不可达场景。第三组样例5 5 1 2 9 2 5 9 1 3 4 3 4 4 4 5 41→2→5 的瓶颈是91→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_queuepairint,int pq默认是最大堆弹出的永远是瓶颈值最大的节点答案会完全错误。必须写成priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq。这个greater太容易被忘。第六个坑是读入性能。当 M 达到 10^5 甚至更高cin默认的同步模式会让输入变慢。解决办法就是ios::sync_with_stdio(false); cin.tie(nullptr);放在 main 函数最前面。如果这行没写某些评测机上会超时。4.2 大数据范围下的性能与内存这类题的数据量在 10^5 附近时二分BFS的时间在零点几秒到一秒出头之间非常稳。BFS每次都要开新的 vis 数组size为 N110^5级别的数组开一次就是一两百KB二分20次也就几MB内存完全没问题。并查集解法则更省只需要 parent 数组和排序后的边数组内存占用最小。有人说二分BFS比并查集多一个 logW 因子会不会更慢实测中不会。因为 W 即便到 10^9logW 也就30左右每次 BFS 都是 O(NM)总操作量在 3×10^6 量级现代评测机一两秒稳稳跑完。担心性能的话优先用并查集排序一次然后线性加边是最少的操作次数。4.3 考场时间分配与答题策略双机位监考的模式下代码很难反复调试所以思路不清晰之前别急着敲键盘。我给自己定的规矩是看到“最小化最大/最大化最小”的题先花三分钟在草稿纸上确认有没有单调性确认有再开始写二分答案。如果确认不是二分再考虑是不是Dijkstra变形、并查集、BFS状态搜索。这道题留25到35分钟比较合理。前10分钟用来读题、建模型、确认输出要求10到20分钟写代码并跑样例剩下的时间构造边界数据自测。边界数据至少要包括单节点图、两个节点直接相连的图、不可达的图、全图边权相等的图。每一组都要想清楚预期输出是多少再拿程序跑一遍。5. 一些题外话这道题教会我的东西我自己做这道题最大的收获不是记住了什么模板而是意识到机试真正考察的是“把自然语言翻译成数学模型”的能力。Alice的安全旅行说得再生动本质就是一张有权无向图上的瓶颈最小化问题。一旦完成这个翻译接下来选二分还是并查集只是个人偏好的问题。另外有一点值得提醒做完这道题后可以顺手把变式也想一遍。如果题目改成“路径上边权总和最小但路径长度不能超过K”那就是分层图加最短路径如果改成“必须经过若干个检查站”那就变成多段最短路的组合问题。机试题目之间联系很紧密吃透一题往往能顺带拿下三五道变种。如果你正准备这类考试建议把二分答案、并查集、Dijkstra变形这三板斧都练熟遇到类似名字的题目先笑一笑然后冷静分析它到底考什么模型。做题的心态稳住代码一遍过的概率就会高很多。