2011-06-16 18:08:34Morris
d667. 820 - Internet Bandwidth
http://zerojudge.tw/ShowProblem?problemid=d667
內容 ：
在網路上有許多節點，點與點之間有連結，相當於是條網路線，網路線可以是雙向的，但是每條都有同時單秒最大負荷量，不過一個點可以同時對很多其他很多點作傳輸，現在要找出點對點的單秒最大傳輸流量，
例如: 現在要從1為起點傳到4為終點，其最大流量為25，分別路徑為1-2-4 流量10，1-3-4 流量10，1-2-3-4 流量5，加起來共25。
輸入說明 ：
有很多筆測資。每一個測資還始會有一個數字代表有幾個節點 n (2 ≤n ≤100)，這 n 個節點分別編號為1~n，接下來的那一行會有3個數字s ，t ，c，分別代表起始節點、目標節點及連線數量。接下來的 c 行每行有三個整數，前兩個整數代表所連接的節點，第三個整數則是頻寬，頻寬為一個不大於 1000 的非負整數。
每兩點之間可能有超過2條的連線，但是不會自己連到自己，以及所有連線都是雙向的，最後輸入0代表結束該筆測資。
輸出說明 ：
對於每一筆測資，首先印出第幾個網路，然後印出 從 s 傳到 t 的最大頻寬，每一組測試資料後都換一行。
範例輸入 ：
41 4 51 2 201 3 102 3 52 4 103 4 200
範例輸出 ：
Network 1The bandwidth is 25.
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: d667 "820 - Internet Bandwidth" from UVa ACM 820 */
/* Language: C */
/* Result: AC (26ms, 318KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-15 22:14:10 */
/**********************************************************************************/
#include<stdio.h>
#define MaxV 10000000
#define MinV 0
int Map[101][101];
int max_flow(int st, int ed, int n) {
int maxflow = 0, tn , tw;
int pre[101], V[101], a, b;
int Q[10001], Qt;
while(1) {
int Used[101] = {};
for(a = 0; a <= n; a++) V[a] = MinV;
V[st] = MaxV;
Qt = 0, Q[0] = st, pre[st] = st;
for(a = 0; a <= Qt; a++) {
tn = Q[a], Used[tn] = 0;
for(b = 1; b <= n; b++) {
tw = (V[tn] < Map[tn][b]) ? V[tn] : Map[tn][b];
if(tw > V[b]) {
V[b] = tw, pre[b] = tn;
if(Used[b] == 0)
Q[++Qt] = b, Used[b] = 1;
}
}
}
if(V[ed] == 0) break;
maxflow += V[ed];
for(a = ed; a != st; a = pre[a]) {
Map[pre[a]][a] -= V[ed], Map[a][pre[a]] += V[ed];
}
}
return maxflow;
}
main() {
int n, m, a, b, v, st, ed, x, y;
int C = 0;
while(scanf("%d", &n) == 1 && n) {
scanf("%d %d %d", &st, &ed, &m);
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++)
Map[a][b] = 0;
for(a = 0; a < m; a++) {
scanf("%d %d %d", &x, &y, &v);
Map[x][y] += v;
Map[y][x] += v;
}
printf("Network %d\n", ++C);
printf("The bandwidth is %d.\n\n", max_flow(st, ed, n));
}
return 0;
}