题解 UVA10099 The Tourist Guide

· · 题解

题目链接 \mathfrak{UVA10099}。
可能更好的阅读体验。

输出格式

如果您是一名饱经 UWaA 摧残的老手，养成了绝不多输出换行的良好习惯，那么恭喜您，本题需要多输出换行。
具体地，如果您是如下写法，特判在所有不是第 1 组的输出前输出换行：

if (++cnt != 1) putchar('\n');
printf("Scenario #%d\nMinimum Number of Trips = ", cnt);
if (num % f[s][t] == 0) printf("%d", num / f[s][t]);
else printf("%d", num / f[s][t] + 1);
putchar('\n');

请改为：

printf("Scenario #%d\nMinimum Number of Trips = ", ++cnt);
if (num % f[s][t] == 0) printf("%d\n", num / f[s][t]);
else printf("%d\n", num / f[s][t] + 1);
putchar('\n');

为您的 AC 献上礼炮。

题目描述

有 N\ (N\le 100) 个城市，城市间有许多条双向通行的道路，每条道路连接两座城市。每条道路还有一个权值 P\ (P>1)，表示在该条道路上行驶的车辆被允许的最大载客量。G 先生是一名导游，他想要亲自把 num 名旅客从 S 城运往 T 城，问 G 先生最少要运多少趟？

如上图，G 先生想要亲自把 99 名旅客从 1 号城运往 7 号城。他应走的路径为 1-2-4-7，路径上最大载客量的最小值为 25，按理运 4 趟即可。但因为 G 先生也是人，所以实际上每次只能运输 24 名旅客，需要运 5 次。

输入格式

本题有多组数据。
对于每组数据：
第一行两个正整数 N 和 M，表示城市数量和道路数量。
接下来 M 行，每行三个正整数 u,v,w，表示城市 u 和城市 v 由一条最大载客量为 w 的道路连接。
最后一行三个正整数 S,T,num，表示要将 num 名旅客从 S 城运往 T 城。
当 N 和 M 为 0 时停止输入。

输出格式

每组数据输出两行：
第一行，输出 “Scenario #x”，x 为当前是第几组数据。
第二行，输出 “Minimum Number of Trips = ans”，ans 为所求答案。
每组输出最后应输出两次换行。

解题思路

题目要求我们找到从 s 通往 t 的各条路径上最小边权的最大值。
如果 s 和 t 是固定的，可以使用复杂度为 O(m\log m) 的最大瓶颈生成树算法。但在此题中 s 和 t 是每组数据自行给定的，所以使用 O(n^3) 的 Floyd 算法。
注意当求出 s 到 t 的最小边权最大值后应将该值减 1，因为导游需要亲自运输旅客，所以实际上每次能够运输的旅客数量为该边权减 1。

AC CODE

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

const int maxn = 1010;

int n, m, s, t, cnt, num, f[maxn][maxn];

int main() {
    while (scanf("%d%d", &n, &m)) {
        if (!n && !m) break;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; ++i) {
            int p1, p2; scanf("%d%d", &p1, &p2);
            scanf("%d", &f[p1][p2]); f[p2][p1] = f[p1][p2];
        }
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) f[i][j] = max(f[i][j], min(f[i][k], f[k][j]));
            }
        }
        scanf("%d%d%d", &s, &t, &num); --f[s][t];
        printf("Scenario #%d\nMinimum Number of Trips = ", ++cnt);
        if (num % f[s][t] == 0) printf("%d\n", num / f[s][t]);
        else printf("%d\n", num / f[s][t] + 1);
        putchar('\n');
    }
    return 0;
}

感谢观赏！