UVa 10099 The Tourist Guide：最大容量路徑與 Floyd-Warshall 變體應用

UVa 10099 The Tourist Guide：旅遊團最少行程規劃

導遊需將 T 位遊客從城市 S 送至城市 D。城市間雙向道路有載客上限 P。每趟行程導遊必須同行，故單趟實際載客量為路徑上最小邊權減一（導遊佔一席）。目標是找出使總行程數最少的路徑。

核心轉化：尋找「最小邊權最大」的路徑

對於任意路徑，其瓶頸容量為路徑上最小邊權。為讓單趟載客量最大化，需在所有 S→D 路徑中，選擇「最小邊權最大」者。此即為經典的 最大容量路徑（Maximum Capacity Path）或 寬度優先搜尋 問題。

Floyd-Warshall 算法改造

標準 Floyd 求最短路徑鬆弛條件為 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。本題改為：

// 經過 k 後，i 到 j 的最大瓶頸容量
mmap[i][j] = max(mmap[i][j], min(mmap[i][k], mmap[k][j]));

初始化 mmap[u][v] = mmap[v][u] = w，其餘為 0。三重迴圈後，mmap[S][D] 即為最大瓶頸容量。

行程數計算

單趟可載遊客數 = 瓶頸容量 - 1（扣除導遊）。總行程數 = ceil(T / (瓶頸容量 - 1))。

完整 AC 代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, q, mmap[110][110];

void floyd() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mmap[i][j] = max(mmap[i][j], min(mmap[i][k], mmap[k][j]));
}

int main() {
    int u, v, w, kase = 1;
    while (~scanf("%d%d", &n, &m)) {
        if (!n && !m) break;
        memset(mmap, 0, sizeof(mmap));
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            mmap[u-1][v-1] = mmap[v-1][u-1] = w;
        }
        floyd();
        scanf("%d%d%d", &u, &v, &w);
        int capacity = mmap[u-1][v-1] - 1;
        int trips = (int)ceil((double)w / capacity);
        printf("Scenario #%d\n", kase++);
        printf("Minimum Number of Trips = %d\n\n", trips);
    }
    return 0;
}

複雜度與替代方案

• Floyd-Warshall：O(N³)，N ≤ 100 完全足夠。
• 改良 Dijkstra（最大堆）：O(M log N)，單源點更優。
• 最大生成樹（Kruskal/Prim）：MST 上任意兩點路徑即為最大容量路徑。

本題是圖論中「最優化最劣條件」典型應用，掌握 Floyd 變體與 MST 性質對解決同類瓶頸問題極有幫助。