UVA 10099 - The Tourist Guide

解題觀念

Floyd-Warshall

可以參考我的課程簡報：MST & Shortest Path
關於 Floyd-Warshall 的基本觀念可以參考我的這篇文章：Algorithm - Floyd-Warshall

題目敘述

分配容量
有位導遊的工作是把遊客從一個城市帶到另個城市
每個城市之間有著雙向的道路，而交通工具是巴士，但巴士有最大載客量限制

請幫忙這位導遊安排以最少的巴士把所有遊客帶到目的地城市

Input

每組測資中
第一行有二整數 N、M
N 表示城市數，M 表示道路樹
接下來有 M 行，每行有三個數字 u、v、w
表示兩端連接的城市及單台巴士最大容克量

最後給予三個整數 S、D、T
S 表示起點城市、D 表示終點城市、T 表示遊客總數

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0

Output

輸出格式為：
Scenario #<當前為第幾筆測資>
Minimum Number of Trips = <最少需要幾趟>

Scenario #1
Minimum Number of Trips = 5

解題思維參考

Solution Code

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100+5;

int main(){
    int N, M;
    int Case = 1;
    while(cin >> N >> M && N && M){

        int u, v, w;
        int dp[maxn][maxn];
        // 初始化不是無限大而是 0
        // 因為期望載客量越大越好 故初始化要是很小的 0
        memset(dp, 0, sizeof(dp));
        
        for(int i = 0; i < M; ++i){
            cin >> u >> v >> w;
            dp[u][v] = dp[v][u] = w;
        }

        // Floyd Warshall
        for(int k = 1; k <= N; ++k){
            for(int i = 1; i <= N; ++i){
                for(int j = 1; j <= N; ++j){
                    dp[i][j] = max(dp[i][j], min(dp[i][k], dp[k][j]));
                }
            }
        }

        int start, end, people;
        cin >> start >> end >> people;

        int ans = (people/(dp[start][end]-1));
        // 減一是因為每次容量都又留一個位置給導遊 可行遊客容量就會少一
        // 如果不能整除 就要多送一趟
        if(people % (dp[start][end]-1) > 0) ans++;

        cout << "Scenario #" << Case++ << endl << "Minimum Number of Trips = " << ans << endl << endl;
    }
}