範例程式碼 uva820

//uva820
#include <iostream>
#include <cstring>
#include <queue>
#define M 105

using namespace std;

int adj[M][M];		// adjacency matrix

int Edmonds_Karp(int s, int t) {
	int f = 0;	  // max flow
	while (true) {  // break until path not found.
		// BFS
		int q[M];			  // BFS queue
		int Path[M];		   // Path for back trace
		int Head = 0, Tail = 0;

		memset(Path, -1, sizeof(Path));
		q[0] = s;
		Path[s] = s;	// Source, back trace end point
		Tail = 1;

		while(Head < Tail && Path[t] == -1) {
			for(int i = q[Head], j = 0; j < M; ++j) {
				if(Path[j] == -1 && adj[i][j] > 0) {
					q[Tail] = j;
					Path[j] = i;
					++Tail;
				}
			}
			++Head;
		}

		// could find a path from s to t.
		if (Path[t] == -1)
			break;

		int df = 2147483647;
		// back tracing find minimum bandwidth
		int i = Path[t], j = t;
		while(i != j) {
			df = min(df, adj[i][j]);
			j = i;
			i = Path[j];
		}
		
		// refresh each link's bandwidth with Min.
		i = Path[t], j = t;
		while(i != j) {
			adj[i][j] -= df;
			adj[j][i] += df;
			j = i;
			i = Path[j];
		}
		f += df;
	}
	return f;
}

int main() {
	int n;
	int ti = 0;
	while(cin >> n && n) {
		memset(adj, 0, sizeof(adj));
		int s, t, c;
		int x, y, b;
		cin >> s >> t >> c;

		for(int i = 0; i < c; ++i) {
			cin >> x >> y >> b;

			// one pair might has multiple link, but all links are bi-connect
			// so combine their bandwidth.
			adj[x][y] += b;
			adj[y][x] += b;
		}

		cout << "Network " << ++ti << endl;
		cout << "The bandwidth is " << Edmonds_Karp(s, t) << "." << endl << endl;
	}
	return 0;
}