Code: Select all
#include "stdio.h"
#include "stdlib.h"
#define MAXN 501
long C[MAXN][MAXN], F[MAXN][MAXN], E[MAXN], H[MAXN];
int N;
int S, T, CC;
bool read(){
scanf("%d", &N);
if(!N)
return 0;
int a, b, c;
scanf("%d%d%d", &S, &T, &CC);
for(int i = 0; i < CC; i++){
scanf("%d%d%d", &a, &b, &c);
C[a][b] += c;
C[b][a] = C[a][b];
}
H[S] = N;
return 1;
}
long flow(){
int i, j;
long tp;
for(i = 1; i <= N; i++)
if(S != i && C[S][i])
F[S][i] = C[S][i], F[i][S] = -C[S][i], E[i] = C[S][i];
while(1){
for(i = 1; i <= N; i++){
if(i == S || i == T)
continue;
if(E[i])
break;
}
if(i >= N)
break;
for(j = 1; j <= N; j++)
if(C[i][j] > F[i][j] && H[j] + 1 == H[i])
break;
if(j <= N){
tp = E[i] > C[i][j] - F[i][j] ? C[i][j] - F[i][j] : E[i];
E[i] -= tp;
E[j] += tp;
F[i][j] += tp;
F[j][i] -= tp;
}
else{
tp = 1000000;
for(j = 1; j <= N; j++)
if(C[i][j] > F[i][j] && H[j] < tp)
tp = H[j];
H[i] = 1 + tp;
}
}
return E[T];
}
/*
void gen(){
FILE *fo = fopen("820.in", "w");
int N = 200;
int M = 30000;
fprintf(fo, "%d\n", N);
fprintf(fo, "%d %d %d\n",1, N, M);
for(int i = 0; i < M;) {
int a = rand()%200 + 1, b = rand()%200 + 1;
if(a!=b){
fprintf(fo, "%d %d %d\n", a, b, rand()%1000);
i++;
}
}
fclose(fo);
}
*/
void clean(){
int i, j;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
C[i][j] = F[i][j] = 0;
for(i = 1; i <= N; i++)
E[i] = H[i] = 0;
}
int main(){
//gen();
//return 0;
#ifndef ONLINE_JUDGE
freopen("820.in", "r", stdin);
freopen("820.out", "w", stdout);
#endif
int nc = 1;
while(read()){
printf("Network %d\nThe bandwidth is %ld.\n\n", nc, flow());
nc++;
clean();
}
return 0;
}