UVA10099 - The Tourist Guide(floyd + 最小值的最大化)

UVA10099 - The Tourist Guide(floyd + 最小值的最大化) 
UVA10099 - The Tourist Guide

题目大意： 
给一无向图，图上的点代表城市，边代表路，每条边上的权值代表的是这条路上的巴士的最大乘客数，作为导游，给定起点和终点，和负责的游客，问需要的最少的趟数可以将这个游客送到终点。

解题思路： 
路径上最小值的最大化。减少趟数，那么就的要求这条路上的可负载乘客量尽量要大，注意每一趟导游都要跟上。floyd最短路过程中，记录下路径上的最大值。 
G【i】【j】 = max(G【i】【j】, min(G【i】【k】+G【k】【j】);

代码：

#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 105;int S, E, NUM;
int G[maxn][maxn];int min (const int a, const int b) {return a < b ? a : b;
}
int Floyd(int N) {for (int k = 1; k <= N; k++)    for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++) {if (G[i][k] == -1 || G[k][j] == -1)continue;if (min(G[i][k], G[k][j]) > G[i][j])G[i][j] = min(G[i][k], G[k][j]);}return G[S][E];
}int main () {int N, R, T = 0;int x, y, num;while (scanf ("%d%d", &N, &R) && (N || R)) {memset(G, -1, sizeof(G));for (int i = 0; i < R; i++) {scanf ("%d %d %d", &x, &y, &num);G[x][y] = G[y][x] = num;}scanf ("%d %d %d", &S, &E, &NUM);       printf ("Scenario #%d\nMinimum Number of Trips = ", ++T);if (S == E) {printf ("0\n\n");continue;}int num = Floyd(N);if (NUM % (num - 1) == 0)printf ("%d\n\n", NUM/(num - 1));elseprintf ("%d\n\n", NUM/(num - 1) + 1);}return 0;
}