这道题和前两天做过的那个噪声污染的题是很类似的,求s到d的所有路径中能通过的最多人数大的路径的流量
那么也是Floyd的思想,如果1和4之间插入了3,使得1到4的流量增加,那么就是插入3
即满足条件:(1,3)> (1,4) && (3,4)>(1,4),取1,3 和3,4中较小的一个作为1,4的新值
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int n, r, s, d, t, map[N][N]; int main() { int icase = 1; while ( scanf("%d%d", &n, &r) != EOF && !( n == 0 && r == 0 ) ) { memset( map, 0, sizeof(map) ); for ( int i = 1; i <= r; ++i ) { int u, v, c; scanf("%d%d%d", &u, &v, &c); map[u][v] = map[v][u] = c; } scanf("%d%d%d", &s, &d, &t); for ( int k = 1; k <= n; ++k ) for ( int i = 1; i <= n; ++i ) for ( int j = 1; j <= n; ++j ) if ( i != k && i != j && j != k && map[i][j] < map[i][k] && map[i][j] < map[k][j] ) map[i][j] = min( map[i][k], map[k][j] ); int ans; map[s][d]--; if ( t%map[s][d] == 0 ) ans = t/map[s][d]; else ans = t/map[s][d] + 1; printf("Scenario #%d\nMinimum Number of Trips = %d\n\n", icase++, ans ); } }