A90626. ANOTHER EXERCISE ON GRAPHS 题解 题意简述 给定 n 个点 m 条边的连通无向带权图。每次查询 (a, b, k)：在 a 到 b 的所有路径中，找一条路径使得路径上第 k 大的边权尽可能小，输出这个最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 核心思路：二分答案 + KRUSKAL 重构 + FLOYD 第一步：转化问题 > 「第 k 大边权最小」 → 二分答案 对答案 mid 进行二分：如果只使用权值 ≤ mid 的边（即"免费边"），从 a 到 b 的最短路（以边数计）是否 < k？ * 如果「最短边数 < k」，说明用 ≤ mid 的边就能覆盖 k-1 条边，第 k 大的边权 ≤ mid，答案可以更小。 * 否则答案需要更大。 但直接对值域二分太慢。注意到答案一定是某条边的权值，所以我们对边权离散化排序后二分即可。 第二步：按边权排序 + KRUSKAL 式逐步加边 将所有 m 条边按权值从小到大排序。按此顺序逐步加入边，每加入一条边后，"免费边"的集合就多了一条。 关键定义： dp[i][j][k]=只使用前 i 条边（按权排序）时，从 j 到 k 的最少边数dp[i][j][k] = \text{只使用前 } i \text{ 条边（按权排序）时，从 } j \text{ 到 } k \text{ 的最少边数} dp[i][j][k]=只使用前 i 条边（按权排序）时，从 j 到 k 的最少边数 但 m 可以很大，不能枚举所有 m 条边。注意到 n ≤ 400，最小生成树只有 n−1 条边。只有 MST 上的边才会真正改变连通性（让某些原本不连通的点对变得连通）。非 MST 边加入时，连通性不变，最短边数不可能变得更优。 > 等等，非 MST 边真的不影响最短边数吗？ 确实会！非 MST 边虽然不改变连通性，但可能提供更短的路径（边数更少）。不过这个代码做了一个巧妙的处理——在 dp[0] 中用 Floyd 求出了初始的全局最短边数（用所有边），然后只对 MST 边做 DP 递推。这是因为： * g[i][j] 存的是用所有边时从 i 到 j 的最短边数（Floyd 求出） * dp[0][i][j] = g[i][j]：初始时"没有免费边"，最短边数就是全图的最短边数 * 然后按 MST 边权从小到大，逐步将 MST 边变为"免费" 第三步：DP 转移 当加入第 i 条 MST 边 (x, y) 时（权值为 wiw_iwi ），它变成"免费边"（权值 ≤ wiw_iwi ，不计入第 k 大），转移： dp[i][j][k]=min(dp[i−1][j][k],dp[i−1][j][x]+dp[i−1][y][k],dp[i−1][j][y]+dp[i−1][x][k])dp[i][j][k] = min \big(dp[i{-}1][j][k], dp[i{-}1][j][x] + dp[i{-}1][y][k], dp[i{-}1][j][y] + dp[i{-}1][x][k] \big) dp[i][j][k]=min(dp[i−1][j][k],dp[i−1][j][x]+dp[i−1][y][k],dp[i−1][j][y]+dp[i−1][x][k]) 含义： * 不经过这条边：dp[i−1][j][k]dp[i{-}1][j][k]dp[i−1][j][k] * 经过这条边 x→y：从 j 到 x 的边数 + 从 y 到 k 的边数（中间这条免费边不计入"需要付费的边数"） * 经过这条边 y→x：对称方向 第四步：查询二分 对每个查询 (a, b, k)，在 MST 边序列上二分找最小的 i，使得 dp[i][a][b]<kdp[i][a][b] < kdp[i][a][b]<k。此时第 i 条 MST 边的权值 wiw_iwi 就是答案。 含义：前 i 条 MST 边都"免费"后，a 到 b 只需要不到 k 条"付费边"，说明第 k 大边权 ≤ wiw_iwi 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码