题目链接: POJ-1459 Power Network http://poj.org/problem?id=1459
题意
有 $np$ 个发电站,$nc$ 个消费者,$m$ 条有向边, 给出每个发电站的产能上限, 每个消费者的需求上限, 每条边的容量上限, 问最大流量.
思路
很裸的最大流问题, 源点向发电站连边, 边权是产能上限, 消费者向汇点连边, 边权是需求上限, 其余的连边按给出的 $m$ 条边加上去即可.
代码实现
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <queue>
- using std::queue;
- const int INF = 0x3f3f3f3f, N = 110, M = N * N * 2;
- int head[N], d[N];
- int s, t, tot, maxflow;
- struct Edge
- {
- int to, cap, nex;
- } edge[M];
- queue<int> q;
- void add(int x, int y, int z) {
- edge[++tot].to = y, edge[tot].cap = z, edge[tot].nex = head[x], head[x] = tot;
- edge[++tot].to = x, edge[tot].cap = 0, edge[tot].nex = head[y], head[y] = tot;
- }
- bool bfs() {
- memset(d, 0, sizeof(d));
- while (q.size()) q.pop();
- q.push(s); d[s] = 1;
- while (q.size()) {
- int x = q.front(); q.pop();
- for (int i = head[x]; i; i = edge[i].nex) {
- int v = edge[i].to;
- if (edge[i].cap && !d[v]) {
- q.push(v);
- d[v] = d[x] + 1;
- if (v == t) return true;
- }
- }
- }
- return false;
- }
- int dinic(int x, int flow) {
- if (x == t) return flow;
- int REST = flow, k;
- for (int i = head[x]; i && REST; i = edge[i].nex) {
- int v = edge[i].to;
- if (edge[i].cap && d[v] == d[x] + 1) {
- k = dinic(v, std::min(REST, edge[i].cap));
- if (!k) d[v] = 0;
- edge[i].cap -= k;
- edge[i^1].cap += k;
- REST -= k;
- }
- }
- return flow - REST;
- }
- void init(int n) {
- tot = 1, maxflow = 0;
- s = n, t = n + 1;
- memset(head, 0, sizeof(head));
- }
- int main() {
- int n, np, nc, m;
- while (~scanf("%d %d %d %d", &n, &np, &nc, &m)) {
- init(n);
- for (int i = 0, u, v, z; i < m; i++) {
- scanf("%*c %d %*c %d %*c %d", &u, &v, &z);
- add(u, v, z);
- }
- for (int i = 0, u, z; i < np; i++) {
- scanf("%*c %d %*c %d", &u, &z);
- add(s, u, z);
- }
- for (int i = 0, u, z; i < nc; i++) {
- scanf("%*c %d %*c %d", &u, &z);
- add(u, t, z);
- }
- while (bfs()) maxflow += dinic(s, INF);
- printf("%d\n", maxflow);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3150207.html