[POJ 1459] Power Network (网络流)
Power Network
题目大意:
有一个电网,其中有N个结点,分为np个发电厂,每个发电厂发电。nc个用户,每个用户要用电。以及N-np-nc个中间站,只负责传送电量。有M条边连接着这些结点,每条边上有最大的电量限制。问用户最多在同一时间可以用多少电?
构造一个超级源点,加上每个源点到发电站的边,边的权值为发电站的发电量。构造一个超级汇点,每个用户到汇点有边,边的权值为用户的用电量。这样就成了一道普通的最大流问题。
/* ID: [email protected] 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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。