您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1459 电网最大流建模详解

編輯：關於C++

问题描述

给定一个电网拓扑，包含发电站、消费者、调度站三类节点及传输线。每个节点有供电上限、发电上限、消费上限。目标：在满足流量平衡、容量约束、节点类型限制下，最大化总消费电量 Con。

网络流建模

节点拆分与超级源汇

原图节点 0 ~ n-1
超级源点 S = n，超级汇点 T = n+1
发电站 i：S → i，容量 = pmax(i)
消费者 j：j → T，容量 = cmax(j)
调度站：不连源汇，仅中转
传输线 (u,v)：u → v，容量 = Lmax(u,v)

约束转化

流量守恒自动满足：
发电站流出 ≤ pmax，消费者流入 ≤ cmax，调度站流入 = 流出，传输线流量 ≤ Lmax。
最大流值即为最大可消费电量 Con。

ISAP 算法实现

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 110;
const int MAXM = 10010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

vector<Edge> edges;
vector<int> G[MAXN];
int n, s, t;
int gap[MAXN], d[MAXN], cur[MAXN], p[MAXN];

void addEdge(int u, int v, int c) {
    edges.emplace_back(u, v, c, 0);
    edges.emplace_back(v, u, 0, 0);
    int m = edges.size();
    G[u].push_back(m - 2);
    G[v].push_back(m - 1);
}

int ISAP() {
    s = n; t = n + 1; n += 2;
    memset(cur, 0, sizeof(cur));
    memset(d, 0, sizeof(d));
    memset(gap, 0, sizeof(gap));
    gap[0] = n;

    int x = s, flow = 0, aug = INF;
    while (d[s] < n) {
        bool advanced = false;
        for (int &i = cur[x]; i < G[x].size(); ++i) {
            Edge &e = edges[G[x][i]];
            if (e.cap > e.flow && d[e.to] + 1 == d[x]) {
                p[e.to] = G[x][i];
                cur[x] = i;
                x = e.to;
                aug = min(aug, e.cap - e.flow);
                if (x == t) {
                    flow += aug;
                    for (int y = t; y != s; y = edges[p[y]].from) {
                        edges[p[y]].flow += aug;
                        edges[p[y] ^ 1].flow -= aug;
                    }
                    aug = INF;
                }
                advanced = true;
                break;
            }
        }
        if (!advanced) {
            int minD = n;
            for (int i = 0; i < G[x].size(); ++i) {
                Edge &e = edges[G[x][i]];
                if (e.cap > e.flow) minD = min(minD, d[e.to]);
            }
            if (--gap[d[x]] == 0) break;
            d[x] = minD + 1;
            gap[d[x]]++;
            cur[x] = 0;
            if (x != s) x = edges[p[x]].from;
        }
    }
    return flow;
}

int main() {
    int np, nc, m;
    while (scanf("%d%d%d%d", &n, &np, &nc, &m) == 4) {
        edges.clear();
        for (int i = 0; i < MAXN; ++i) G[i].clear();

        for (int i = 0; i < m; ++i) {
            int u, v, z;
            scanf(" (%d,%d)%d", &u, &v, &z);
            addEdge(u, v, z);
        }
        for (int i = 0; i < np; ++i) {
            int u, z;
            scanf(" (%d)%d", &u, &z);
            addEdge(n, u, z); // 超级源点编号为 n
        }
        for (int i = 0; i < nc; ++i) {
            int u, z;
            scanf(" (%d)%d", &u, &z);
            addEdge(u, n + 1, z); // 超级汇点编号为 n+1
        }

        printf("%d\n", ISAP());
    }
    return 0;
}