UVA 10048 Audiophobia：Floyd-Warshall 求最小化最大邊權路徑

算法流程

1. 初始化 dist[i][j] = INF (i≠j)，dist[i][i] = 0，邊 dist[u][v] = dist[v][u] = w。
2. 三層循環 k, i, j：
   dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))
3. 查詢直接輸出 dist[s][t]（若為 INF 輸出 no path）。

代碼實現

#include 
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int dist[MAXN][MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, S, Q, tc = 0;
    while (cin >> C >> S >> Q, C||S||Q) {
        if (tc++) cout << '\n';
        for (int i = 1; i <= C; i++)
            for (int j = 1; j <= C; j++)
                dist[i][j] = (i==j) ? 0 : INF;
        for (int i = 0; i < S; i++) {
            int u, v, w; cin >> u >> v >> w;
            dist[u][v] = dist[v][u] = min(dist[u][v], w);
        }
        for (int k = 1; k <= C; k++)
            for (int i = 1; i <= C; i++)
                for (int j = 1; j <= C; j++)
                    if (dist[i][k] != INF && dist[k][j] != INF)
                        dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
        cout << "Case #" << tc << '\n';
        while (Q--) {
            int u, v; cin >> u >> v;
            if (dist[u][v] == INF) cout << "no path\n";
            else cout << dist[u][v] << '\n';
        }
    }
    return 0;
}

複雜度

• Floyd：O(C³) = 10⁶，C=100 極快。
• 查詢：O(1)。
• 空間：O(C²)。

變體與擴展

• 若邊數較少，可用最小生成樹 (MST)：MST 上任意兩點路徑的最大邊權即為答案（MST 性質）。用 Kruskal + LCA 或並查集離線查詢，O(S log S + Q α(C))。
• 本題 C=100，Floyd 最簡潔，代碼量最小。

總結

UVA 10048 是 Floyd-Warshall 變體的經典例題：路徑代價 = 最大邊權，目標 = 最小化代價。只需將標準 Floyd 的 d[i][j] = min(d[i][j], d[i][k]+d[k][j]) 改為 d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))。掌握此變體，可解決大類「瓶頸路徑」、「最小化最大代價」問題。