Alice的安全旅行：图论最大最小路径问题的两种C++解法

『2026 双机位 C 卷 · Alice 的安全旅行』名字听上去像一道情景题但读完题面就能明白它考察的是图论里非常经典的最大最小路径问题。我在集中刷某大厂 OD 机试真题时明显感觉到这类题出现频率很高因为它能同时考察建图能力、最短路径思维和排序算法基本功一题就能筛掉不少人。接下来我会把这道题从读题到拿满分的完整链路讲清楚包含两种可直接提交的 C 写法、时间复杂度的对比以及我在实际刷题中踩过的各种坑。无论你是刚开始准备 OD 机试还是想补一补图论模板这篇都值得仔细看。1. 题目到底在问什么Alice 的安全旅行1.1 还原题面与输入输出我记忆中的题面大致是这样一片风景区里有 N 个观景点编号从 0 到 N-1观景点之间有 M 条双向步道每条步道都有一个安全评分分数越高代表越安全。Alice 希望从起点 S 走到终点 T她选择一条路线时并不会简单考虑走过的总长度而是把整条路线里“最危险的那一段”当作这条路线的评价标准。也就是说如果一条路线由三段组成安全分分别是 80、90、20那么这条路线在 Alice 眼里就只有 20 分因为那一小段会让她非常不安。她想要找出一条路线让这个“最低分”尽可能高。若 S 无法到达 T则输出 -1。输入格式一般是第一行N M S T 接下来 M 行u v w数据范围常见是这样2 ≤ N ≤ 2000001 ≤ M ≤ 2000000 ≤ u, v Nu ≠ v1 ≤ w ≤ 10000000000 ≤ S, T N为什么要把数值范围写得这么大因为机考往往直接给你大数据压力测试如果算法复杂度是 O(N²) 就会超时。这也是本题设计的第一个陷阱。1.2 通过一个样例把结论算出来先别急着写代码手动算一下样例5 6 0 4 0 1 30 0 2 70 1 2 20 1 3 40 2 3 60 3 4 50从 0 到 4 有几条可能路径0 → 1 → 3 → 4安全分依次 30、40、50瓶颈是 30。0 → 2 → 3 → 4安全分依次 70、60、50瓶颈是 50。0 → 2 → 1 → 3 → 4安全分依次 70、20、40、50瓶颈是 20。0 → 1 → 2 → 3 → 4安全分依次 30、20、60、50瓶颈是 20。最佳的是第二条路线输出 50。这里的反直觉之处在于我们不是选最短路径也不是把边权相加而是选“最小边权”最大的那条路线。如果没转过弯来很容易把这道题写成最短路的变体然后样例对不上。2. 核心思路把“安全”抽象成图论瓶颈2.1 数学化之后的定义把观景点看作节点把步道看作无向边每条边有一个权值 w。一条路径 P 的安全值定义为min(e1.w, e2.w, ..., ek.w)我们要最大化这个东西。这就是经典的“最大最小路径”问题也叫 widest path problem。这种问题在通信网络、交通规划里非常常见比如你要在两个城市之间传输数据每条链路带宽不一样你希望找到一条带宽瓶颈最高的路径。用人话说一条铁链能承受多少拉力取决于它最薄弱的那一环Alice 的安全感也取决于最危险的那一段。想通这一点后面算法就顺了。2.2 三种可行解法的取舍这个题至少有三条路可以走。解法核心思想时间复杂度代码量二分答案 BFS/DFS假设答案至少是 X只用 w≥X 的边判断连通性O(log(1e9) × (NM))很少优先队列 Dijkstra 变形把“最短距离”改为“最大瓶颈”O((NM)logN)中等按权值降序 并查集从大到小开通道路第一次连通时的边权就是答案O(MlogM)很少笔试时我一般会优先考虑并查集其次是 Dijkstra 变形。二分BFS 也可以但多一个 log一般不会超时却容易因为细节写慢。我接下来会把两种最常用的完整代码贴出来。3. 解法一优先队列 Dijkstra 变形C 完整实现3.1 可直接提交的代码#include bits/stdc.h using namespace std; struct Edge { int to; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, S, T; cin N M S T; vectorvectorEdge g(N); for (int i 0; i M; i) { int u, v; long long w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } // best[u]从 S 到 u 的所有路径中能得到的最大“最小安全分” vectorlong long best(N, -1); // 大顶堆first 越大越先弹出 priority_queuepairlong long, int pq; best[S] LLONG_MAX; // 起点没有瓶颈 pq.push({best[S], S}); while (!pq.empty()) { auto [cur, u] pq.top(); pq.pop(); // 如果这个状态已经不是最优直接跳过 if (cur best[u]) continue; // 到达终点即可输出因为是优先队列第一次弹出的终点一定是全局最大 if (u T) { cout cur \n; return 0; } for (const auto e : g[u]) { // 走到 v 的瓶颈 min(到 u 的瓶颈, 当前边权) long long candidate min(cur, e.w); if (candidate best[e.to]) { best[e.to] candidate; pq.push({candidate, e.to}); } } } cout -1 \n; return 0; }3.2 为什么内层判断是 min不是加法这里最容易出问题。很多人写题时会下意识套最短路的模板写成candidate cur e.w但本题的路径值是“取最小值”不是“求和”。比如你从 S 走到某个点 U 时整条路线的最低安全分是 70再通过一条安全分只有 20 的边走到 V那么新路线的最低安全分立刻变成 20而不是 90。反过来如果你目前的分值是 30走一条 100 分的边新路线的最低分仍然是 30不会提高。这就是min(cur, e.w)的原因。优先队列默认按 first 从大到小排列所以我们取到的一定是当前“最大瓶颈”的状态。如果一条边能更新更大的 best 值就入队如果某个旧状态已经被更好的状态覆盖cur best[u]时会直接跳过。这是 Dijkstra 变体里通用的惰性删除技巧能避免同一节点反复被无效处理。3.3 复杂度为什么能放心过在带正权这里表现为“越大越优”的情况下每个节点出队的次数是有界的。最坏情况下复杂度是 O((NM) log N)。在 N20 万、M20 万的限制内C 版本完全可以在一秒多一点的时间内跑完。机考环境通常会给 2 到 4 秒所以这个写法不会成为性能瓶颈。4. 解法二按边权值排序 并查集笔试更稳的选择4.1 直觉从最安全的路径开始解锁换一个角度想假设安全问题可以拆开处理我们把所有道路按照安全分从高到低排序。先只开通那些最安全的道路看 Alice 能不能从 S 走到 T不能就继续降低标准把第二安全的道路也开通再把第三安全的道路也开通……直到某一次开通了一条道路后S 和 T 恰好连通那么这条路的安全分就是 Alice 能拿到的最好成绩。这个直觉如果用并查集实现非常优雅每次开通一条边就把两个端点所在的集合合并。每次合并后判断find(S)和find(T)是否相同。一旦相同直接输出当前边的权值。为什么第一次连通时的边权就是答案因为边是按照安全分从大到小处理的。假设当前边是 w50那么在这条边之前开通的所有边的安全分都 ≥ 50S 和 T 恰好因为这条边连通说明路径上所有边都不小于 50且其中至少有一条是 50。如果答案是 51那么只开通安全分 ≥51 的边时S 和 T 不应该连通但之前没有连通所以 50 正是临界点。4.2 并查集 排序 C 代码#include bits/stdc.h using namespace std; struct DSU { vectorint parent, sz; DSU(int n) : parent(n), sz(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] x ? x : parent[x] find(parent[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); parent[b] a; sz[a] sz[b]; return true; } }; struct Edge { int u, v; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, S, T; cin N M S T; vectorEdge edges(M); for (int i 0; i M; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(N); for (const auto 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; }需要提醒的是如果题目输入节点从 1 开始编号建 DSU 时要用 N1读入后把 u、v 减一示例直接按 0 索引写考场上一旦发现越界就要立刻检查这里。4.3 两种解法怎么选如果题目只要求输出“最大最小安全值”我会选并查集因为不容易出逻辑错。如果题目额外要求输出具体路线那就用 Dijkstra 变形在更新 best 时用parent[v] u记录前驱最后从 T 回溯出来。如果担心数据范围巨大导致路径回溯占用内存那么也可以用二分BFS 顺带记录父节点。笔试很少有题会真的让你打印一条巨长的路径所以不必过度担心。5. 高发错误与实战排查5.1 最容易被扣分的几个点第一起点等于终点。这种边界很多人不处理。通常题面会约定如果 STAlice 不需要走任何路答案可以认为是 0。但有些题面会定义为“安全分无限大”或直接输出 0最稳妥的办法是拿到题先看边界说明没有说明的话输出 0 是大多数题目的判题逻辑。第二1 索引还是 0 索引。看起来只是减一的问题实际上引发的问题很隐蔽如果节点 0 作为哨兵被占用find 和 best 数组可能出错。我建议拿到题直接假设 0 索引读入 u、v 后立即减一后续不再纠结。第三错误套最短路求和模板。前面强调过不是cur e.w而是min(cur, e.w)。如果把这条写错小样例可能侥幸通过大数据绝对会挂。第四不连通时输出什么。无论哪种解法最终遍历完所有状态后都要补一个 -1否则数组会越界或者输出空内容。5.2 自测用例速查表我建议把这些用例塞进本地文件里改一次代码就跑一遍。很多时候你以为写对了实际上只过了样例多造几个极端 case尤其是 N1 或 ST能救回不少分。场景输入预期输出正常连通上面 5 节点样例50完全不可达3 1 0 2然后0 1 100-1起点等于终点2 0 1 1没有更多行0按约定链式大权重2 1 0 1然后0 1 999999999999999999多条路径选择4 4 0 3然后0 1 5、1 3 5、0 2 8、2 3 885.3 双机位机考环境下的一些应试经验现在很多大厂的 OD 机考都采用双机位监考电脑前置摄像头对着人侧后方再用手机或摄像头对着桌面和屏幕。这意味着考试时别指望靠搜索或者传答案代码能力必须提前练到“肌肉记忆”。我的方法是把常用模板压缩成几段并查集模板、Dijkstra/优先队列模板、二分答案模板、快读和链式前向星模板。每天手敲一遍连续练三五天看见题就能直接套。遇到图论题先把 N 和 M 读出来判断是稠密图还是稀疏图再决定邻接矩阵、邻接表还是链式前向星。这种判断甚至比算法本身更重要。外加时间分配前两题基础题尽量 20 分钟内拿满给第三题留出至少 40 分钟。如果第三题没有思路先把暴力样例打出来理清边界再用二分或 DFS 把一部分测试点救回来。机考判分通常按测试点算一个极端 case 没处理就差好几分。6. 写给自己也写给你的复盘这道题我至少练了三遍第一次用并查集第二次用 Dijkstra 变形第三次用二分BFS 做对拍验证。三遍下来最大的感受是所谓“会做图论题”其实不是背下某个算法而是能在看到“安全”“最大”“最小”“起点终点”这些词时第一时间建立起路径模型。每次刷完一道题我会用一句话总结它的考点比如“这个是最大最小路径并查集直接秒”“这个是最短路径变形要注意用堆优化”。这个习惯练多了见到新题就不慌。最后再分享一个小技巧刷题复盘时把解法一和解法二的代码放在一起用同一组测试数据跑一遍输出互相验证。两个完全不同的实现如果结果一致基本上代码就是稳的如果不一致往往是你题干理解有偏差而不是编译错误。希望这篇能帮你把 Alice 的安全旅行彻底搞定也愿你在真正上考场时碰到类似题能一眼看穿它的本质。