程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ 1459] Power Network (網絡流）

[POJ 1459] Power Network (網絡流）

編輯：C++入門知識

Power Network

題目大意：

有一個電網，其中有N個結點，分為np個發電廠，每個發電廠發電。nc個用戶，每個用戶要用電。以及N-np-nc個中間站，只負責傳送電量。有M條邊連接著這些結點，每條邊上有最大的電量限制。問用戶最多在同一時間可以用多少電？

解題思路：

構造一個超級源點，加上每個源點到發電站的邊，邊的權值為發電站的發電量。構造一個超級匯點，每個用戶到匯點有邊，邊的權值為用戶的用電量。這樣就成了一道普通的最大流問題。

/*
ID: [email protected]
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; }