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] = \text{只使用前 } i \text{ 条边（按权排序）时，从 } j \text{ 到 } k \text{ 的最少边数}$$

但 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) 时（权值为 $w_i$），它变成"免费边"（权值 ≤ $w_i$，不计入第 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{-}1][j][k]$
• 经过这条边 x→y：从 j 到 x 的边数 + 从 y 到 k 的边数（中间这条免费边不计入"需要付费的边数"）
• 经过这条边 y→x：对称方向

第四步：查询二分

对每个查询 (a, b, k)，在 MST 边序列上二分找最小的 i，使得 $dp[i][a][b] < k$。此时第 i 条 MST 边的权值 $w_i$ 就是答案。

含义：前 i 条 MST 边都"免费"后，a 到 b 只需要不到 k 条"付费边"，说明第 k 大边权 ≤ $w_i$。

---

逐行注释代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int t, n, m, q;
int c[405][405];                           // c[i][j]: 原图 i→j 的边权（用于存储，本代码未深度使用）
int g[405][405];                           // g[i][j]: 用所有边时 i→j 的最少边数（Floyd 求）
int dp[405][405][405];                     // dp[i][j][k]: 前 i 条 MST 边免费后，j→k 的最少边数
int fa[405];                               // 并查集父数组

struct node {
    int x, y, z;                           // 边的两端点 x,y 和权值 z
} a[N], b[405];                            // a[]: 所有边，b[]: MST 边

bool cmp(node x, node y) {
    return x.z < y.z;                      // 按边权从小到大排序
}

int find(int x) {                          // 并查集查找（路径压缩）
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> m >> q;

        // ========== 初始化 ==========
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[0][i][j] = 1e9;        // 初始最少边数设为无穷大
                c[i][j] = 1e9;            // 边权设为无穷大
                g[i][j] = 1e9;            // 最少边数设为无穷大
            }
        }
        for (int i = 1; i <= n; i++) {
            dp[0][i][i] = 0;              // 自己到自己，0 条边
            c[i][i] = 0;
            g[i][i] = 0;
            fa[i] = i;                     // 并查集初始化
        }

        // ========== 读入边 ==========
        for (int i = 1; i <= m; i++) {
            cin >> a[i].x >> a[i].y >> a[i].z;
            // g[][] 初始化为边数 = 1（每条边算 1 条）
            g[a[i].x][a[i].y] = g[a[i].y][a[i].x] = 1;
            // c[][] 记录边权（取 min 处理重边，虽然题目说无重边）
            c[a[i].x][a[i].y] = min(c[a[i].x][a[i].y], a[i].z);
            c[a[i].y][a[i].x] = min(c[a[i].y][a[i].x], a[i].z);
        }

        // ========== Kruskal 求 MST ==========
        sort(a + 1, a + 1 + m, cmp);       // 按边权排序
        int ll = 0;                         // MST 边计数
        for (int i = 1; i <= m; i++) {
            int x = a[i].x, y = a[i].y;
            x = find(x); y = find(y);
            if (x != y) {                   // 不在同一连通块
                fa[x] = y;                 // 合并
                ll++;
                b[ll] = a[i];              // 记录 MST 边（已按权从小到大）
            }
        }

        // ========== Floyd 求全图最短边数 ==========
        // g[i][j] = 从 i 到 j 的最少经过边数（用所有边）
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

        // dp[0] = 没有免费边时的最短边数（就是全图最短边数）
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[0][i][j] = g[i][j];

        // ========== DP：逐步将 MST 边变为免费 ==========
        for (int i = 1; i <= ll; i++) {
            int x = b[i].x, y = b[i].y;    // 第 i 条 MST 边 (x, y)
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    dp[i][j][k] = min(
                        dp[i-1][j][k],      // 不经过这条免费边
                        min(
                            dp[i-1][j][x] + dp[i-1][y][k],  // 经过 x→y 方向
                            dp[i-1][j][y] + dp[i-1][x][k]   // 经过 y→x 方向
                        )
                    );
                }
            }
        }

        // ========== 查询：二分 MST 边编号 ==========
        while (q--) {
            int x, y, z;
            cin >> x >> y >> z;             // 查询 (a=x, b=y, k=z)

            // 二分找最小的 i，使得 dp[i][x][y] < z
            // 即"前 i 条 MST 边免费后，x→y 只需不到 z 条付费边"
            int l = 1, r = ll, ans = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (dp[mid][x][y] < z) {    // 免费边够多，第 k 大可以更小
                    ans = mid;
                    r = mid - 1;            // 尝试更少的免费边
                } else {
                    l = mid + 1;            // 需要更多免费边
                }
            }
            cout << b[ans].z << " ";        // 答案是第 ans 条 MST 边的权值
        }
        cout << "\n";
    }
    return 0;
}