1459 Power Network

題意：
    有發電站(只發電不耗電)，中繼站(不發電不耗電)，和用電站(只耗電不發電)三種node，題目求所有用電站耗電量總和的最大値。
    輸入第一行有4個數字，n np nc m，n表示共有n站，np為發電站數量，nc為用電站數量，m為有m條電線。
    接下來有m組(u,v)z，表示u到v該電線的容量為z。然後有np個(u)z表示編號u發電站發電量為z；再接下來有nc個u(z)表示編號u為用電站最大用電量為z。
想法：
    最大流模板題，用super source串起所有發電站，super sink串起所有用電站。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	int bfs(int N, int S, int T);
	int cap[105][105], flow[105][105];
	int bottleneck[105], pre[105];
	int main()
	{
	int n;
	int np, nc, M;
	while (scanf("%d %d %d %d", &n, &np, &nc, &M) == 4) {
	// Initial
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	int S = n , // super source
	T = n + 1; // super sink
	// Input
	int u, v, z;
	for (int i = 0; i < M; ++i) {
	scanf(" (%d,%d)%d", &u, &v, &z);
	cap[u][v] += z;
	}
	for (int i = 0; i < np; ++i) {
	scanf(" (%d)%d", &u, &z);
	cap[S][u] += z;
	}
	for (int i = 0; i < nc; ++i) {
	scanf(" (%d)%d", &u, &z);
	cap[u][T] += z;
	}
	// Output
	printf("%d\n", bfs(n+2, S, T));
	}
	}
	int bfs(int N, int S, int T)
	{
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(S);
	bottleneck[S] = 9999999999;
	while (!Q.empty()) {
	int cur = Q.front(); Q.pop();
	for (int nxt = 0; 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];
	}
	result += bottleneck[T];
	}
	return result;
	}

view raw [POJ] 1459 Power Network.cpp hosted with ❤ by GitHub