BZOJ 2165 大樓：倍增 Floyd 解決長度約束最短路

問題描述

給定有向圖，邊權為長度。求從 1 號點出發，總長度 ≥ K 的路徑中，經過最少邊數。n ≤ 100，K ≤ 10¹⁸。

倍增思想

預處理 f[p][i][j]：走 2^p 步從 i 到 j 的最大長度。
遞推：f[p][i][j] = max_k (f[p-1][i][k] + f[p-1][k][j])（類似矩陣乘法，取 max 而非加）。

貪心構造答案

維护 g[i][j]：當前已走步數下，從 i 到 j 的最大長度。初始 g[i][i]=0，其餘 -INF。
從高位到低位嘗試加入 2^p 步：
計算 t[i][j] = max_k (g[i][k] + f[p][k][j])
若 t[1][*] 全 < K，則確認加入這 2^p 步，更新 g=t，答案加 2^p。
最後再走一步即達標，答案 +1。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const long long INF = 4e18;
long long f[62][MAXN][MAXN], g[MAXN][MAXN], t[MAXN][MAXN];
int n; long long K;

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> K;
        // 初始化
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j) {
                long long x; cin >> x;
                f[0][i][j] = x ? x : -INF;
            }
        for (int i=1; i<=n; ++i) f[0][i][i] = max(f[0][i][i], 0LL);
        // 倍增預處理
        int P = 0;
        while ((1LL<=0; --p) {
            // 計算 t = g * f[p]
            for (int i=1; i<=n; ++i)
                for (int j=1; j<=n; ++j)
                    t[i][j] = -INF;
            for (int k=1; k<=n; ++k)
                for (int i=1; i<=n; ++i)
                    for (int j=1; j<=n; ++j)
                        t[i][j] = max(t[i][j], g[i][k] + f[p][k][j]);
            // 檢查是否還需繼續
            bool need = true;
            for (int j=1; j<=n; ++j)
                if (t[1][j] >= K) { need = false; break; }
            if (need) {
                memcpy(g, t, sizeof(g));
                ans += 1LL<

關鍵點

「最大長度」而非最短路，因為要達到 ≥K，越長越容易滿足
倍增矩陣乘法：f[p] = f[p-1] ⊗ f[p-1]（max-plus 半環）
貪心從高位嘗試：不超標就加入，類似二分答案構造
-INF 用 4e18 避免溢出，memcpy 加速數組複製


此題是「倍增 + 矩陣乘法 + 貪心構造」的高級應用，將路徑長度約束轉化為步數最小化問題。