UVa 820 Network Bandwidth

題意：
    求S到T的最大流量為多少。網路是雙向連接的，但共用頻寬，例如A B 10，則A到B的流量+B到A的流量要小於等於10。另外這題給測資的方式會有可能給你很多組A B Xi，所以A到B的頻寬要把Xi全部加起來，例如底下例子1~2的頻寬為30。
2
1 2 2
1 2 10
1 2 20
想法：
    Maximum Flow模板題。

	#include <cstdio>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int cap[101][101];
	int flow[101][101];
	int bottleneck[101], pre[101];
	int bfs(int N, int S, int T);
	int main()
	{
	int N, S, T, C, Case = 1;
	while (scanf("%d", &N) && N) {
	for (int i = 1; i <= N; ++i) {
	fill(cap[i], cap[i]+N+1, 0);
	fill(flow[i], flow[i]+N+1, 0);
	}
	scanf("%d %d %d", &S, &T, &C);
	int a, b, bandwidth;
	for (int i = 0; i < C; ++i) {
	scanf("%d %d %d", &a, &b, &bandwidth);
	cap[b][a] = (cap[a][b] += bandwidth);
	}
	printf("Network %d\n", Case++);
	printf("The bandwidth is %d.\n\n", bfs(N, S, T));
	}
	}
	int bfs(int N, int S, int T)
	{
	int result = 0;
	while (1) {
	fill(bottleneck, bottleneck+N+1, 0);
	queue<int> Q;
	Q.push(S);
	bottleneck[S] = 999999999;
	while (!Q.empty() && bottleneck[T] == 0) {
	int cur = Q.front(); Q.pop();
	for (int nxt = 1; nxt <= N; ++nxt) {
	if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
	Q.push(nxt);
	pre[nxt] = cur;
	bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
	}
	}
	}
	if (bottleneck[T] == 0) break;
	for (int cur = T; cur != S; cur = pre[cur]) {
	flow[pre[cur]][cur] += bottleneck[T];
	flow[cur][pre[cur]] -= bottleneck[T]; // opposite edge
	}
	result += bottleneck[T];
	}
	return result;
	}

view raw [UVa] 820 Internet Bandwidth_bfs.cpp hosted with ❤ by GitHub