UVA 10048 Audiophobia：Floyd 變形求最小最大聲強路徑

問題描述

給定城市地圖（節點為路口，邊為街道，權重為分貝值）。從路口 A 到 G，路徑上的**最大聲強**決定你必須忍受的音量。求任意兩點間路徑的**最小可能最大聲強**（即最小化路徑上的最大邊權）。若無路徑輸出 "no path"。

核心洞察：Floyd 變形

標準 Floyd 求最短路（邊權和最小）。本題需求**最小化路徑上的最大邊權**，轉移方程：

dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));

• dis[i][j]：i 到 j 的最小最大聲強。
• 經過 k 時，路徑最大聲強為 max(dis[i][k], dis[k][j])。
• 取所有中轉點 k 的最小值。

演算法流程

1. 初始化 dis[i][j] = INF，dis[i][i] = 0。
2. 讀入邊，無向圖 dis[u][v] = dis[v][u] = w。
3. 三層迴圈 k, i, j 執行變形 Floyd。
4. 查詢直接輸出 dis[a][b]（若為 INF 則 "no path"）。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 20000000;
const int MAXC = 105;
int dis[MAXC][MAXC];

int main() {
    int C, S, Q, cas = 1;
    while (scanf("%d%d%d", &C, &S, &Q) == 3 && (C || S || Q)) {
        if (cas != 1) printf("\n");
        printf("Case #%d\n", cas++);

        for (int i = 1; i <= C; i++)
            for (int j = 1; j <= C; j++)
                dis[i][j] = (i == j) ? 0 : INF;

        for (int i = 0; i < S; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            dis[u][v] = dis[v][u] = w;
        }

        // Floyd 變形
        for (int k = 1; k <= C; k++)
            for (int i = 1; i <= C; i++)
                for (int j = 1; j <= C; j++)
                    dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));

        for (int i = 0; i < Q; i++) {
            int a, b; scanf("%d%d", &a, &b);
            if (dis[a][b] == INF) printf("no path\n");
            else printf("%d\n", dis[a][b]);
        }
    }
    return 0;
}

複雜度分析

• 時間：O(C³)，C ≤ 100 完全可行（10⁶ 操作）。
• 空間：O(C²)。

關鍵點總結

• **最小化最大值**問題，Floyd 轉移用 max 代替 +，min 保持不變。
• 適用於「膽小鬼走迷宮」、「最大載重路徑」等同類模型。
• 多測資輸出格式：案例間空行，案例編號從 1 開始。

延伸思考

若邊數極少（稀疏圖），可用 **Kruskal 重構樹** 或 **最小生成樹 + LCA** 實現 O((V+E) log V) 查詢，但 C=100 時 Floyd 最簡潔好寫。