Power Network
题目大意：
有一个电网，其中有N个结点，分为np个发电厂，每个发电厂发电。nc个用户，每个用户要用电。以及N-np-nc个中间站，只负责传送电量。有M条边连接着这些结点，每条边上有最大的电量限制。问用户最多在同一时间可以用多少电？
构造一个超级源点，加上每个源点到发电站的边，边的权值为发电站的发电量。构造一个超级汇点，每个用户到汇点有边，边的权值为用户的用电量。这样就成了一道普通的最大流问题。
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#define maxn 140
#define maxm 100000
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
struct node {
int v, f, nxt;
}e[maxm * 2];
int n, m, st, ed, g[maxn], cnt, np, nc;
void add(int u, int v, int c) {
e[++cnt].v = v;
e[cnt].f = c;
e[cnt].nxt = g[u];
g[u] = cnt;
e[++cnt].v = u;
e[cnt].f = 0;
e[cnt].nxt = g[v];
g[v] = cnt;
}
void init() {
mem(g, 0);
cnt = 1;
int u, v, c;
char ch;
st = n, ed = n + 1;
for (int i = 0; i < m; i++) {
while(getchar() != ‘(‘) ;
scanf("%d,%d)%d", &u, &v, &c);
add(u, v, c);
}
for (int i = 0; i < np; i++) {
while(getchar() != ‘(‘) ;
scanf("%d)%d", &v, &c);
add(st, v, c);
}
for (int i = 0; i < nc; i++) {
while(getchar() != ‘(‘) ;
scanf("%d)%d", &u, &c);
add(u, ed, c);
}
}
int vis[maxn], dis[maxn], q[maxn];
void bfs() {
mem(dis, 0);
int font = 0, rear = 1;
q[font] = st;
vis[st] = 1;
while(font < rear) {
int u = q[font++];
for (int i = g[u]; i; i = e[i].nxt) if (e[i].f && !vis[e[i].v]) {
q[rear++] = e[i].v;
vis[e[i].v] = 1;
dis[e[i].v] = dis[u] + 1;
}
}
}
int dfs(int u, int delta) {
if (u == ed) return delta;
else {
int ret = 0;
for (int i = g[u]; i && delta; i = e[i].nxt) if (e[i].f && dis[e[i].v] == dis[u] + 1) {
int dd = dfs(e[i].v, min(delta, e[i].f));
e[i].f -= dd;
e[i ^ 1].f += dd;
delta -= dd;
ret += dd;
}
return ret;
}
}
int maxflow() {
int ret = 0;
while(1) {
mem(vis, 0);
bfs();
if (!vis[ed]) return ret;
ret += dfs(st, INF);
}
}
int main ()
{
while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) {
init();
printf("%d\n", maxflow());
}
return 0;
}