Power Network

题目大意：

有一个电网，其中有N个结点，分为np个发电厂，每个发电厂发电。nc个用户，每个用户要用电。以及N-np-nc个中间站，只负责传送电量。有M条边连接着这些结点，每条边上有最大的电量限制。问用户最多在同一时间可以用多少电？

解题思路：

构造一个超级源点，加上每个源点到发电站的边，边的权值为发电站的发电量。构造一个超级汇点，每个用户到汇点有边，边的权值为用户的用电量。这样就成了一道普通的最大流问题。

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include

#include #include #include #include #include #include #include #include #include #include #include #include #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 , maxflow()); } return 0; }

[POJ 1459] Power Network (网络流）

Power Network

题目大意：