首页 > > 程序设计 > C/C++ >

网络流之最大流EK --- poj 1459

2019-05-22 06:28:01来源：博客园阅读 ()

题目链接

本篇博客延续上篇博客（最大流Dinic算法）的内容，此次使用EK算法解决最大流问题。

EK算法思想：在图中搜索一条从源点到汇点的扩展路，需要记录这条路径，将这条路径的最大可行流量 liu 增加到结果ans中，然后反向从汇点到源点更新这条路径上的每条边的权值（减去此次的liu），同时反向边的权值也需要更新（加上此次的liu）。然后再搜索新的扩展路……，循环，直到找不到新的扩展路，此时的ans就是最大流了。

注：EK算法解决最大流时，我看别人都是使用矩阵建立的图，这样反向更新扩展路径上的边权时，只需要之前记录每个点的父亲节点即可。我是在前一篇的Dinic的前向星代码上修改为EK算法，由父亲和孩子节点编号不能直接得出连接的边号，所以需要另外用一个变量 edgeIndex[v] 记录从 u 到 v 的边号，这样方便反向修改边权值。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
const int N = 105;
const int MAXN = 0x3fffffff;

struct Edge {
    int to;
    int value;
    int next;
}e[2 * N*N];
int head[N], cnt;
int p[N], fa[N], edgeIndex[N];
int n, np, nc, m;

void insert(int u, int v, int value) {
    e[++cnt].to = v;
    e[cnt].value = value;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void init() {
    memset(head, -1, sizeof(head));
    cnt = -1;
}

int BFS() {
    int ans = 0;
    while (1)
    {
        memset(p, -1, sizeof(p));
        queue<int> Q;
        Q.push(0);
        p[0] = MAXN;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int edge = head[u]; edge != -1; edge = e[edge].next) {
                int v = e[edge].to;
                if (p[v] ==-1 && e[edge].value > 0) {
                    p[v] = min(p[u], e[edge].value);
                    fa[v] = u;
                    edgeIndex[v] = edge;
                    Q.push(v);
                    if (v == n + 1) goto endw;
                }
            }
        }
    endw:;
        if (p[n+1] == -1) return ans;
        else {
            ans += p[n + 1];
            int x = n + 1;
            while (x) {
                int edge = edgeIndex[x];
                e[edge].value -= p[n + 1];
                e[edge ^ 1].value += p[n + 1];
                x = fa[x];
            }
        }
    }
}



int main()
{
    while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) {
        init();
        int u, v, z;
        for (int i = 0; i < m; i++) {
            scanf(" (%d,%d)%d", &u, &v, &z);
            insert(u + 1, v + 1, z);
            insert(v + 1, u + 1, 0);
        }
        for (int i = 0; i < np; i++) {
            scanf(" (%d)%d", &u, &z);
            insert(0, u + 1, z);
            insert(u + 1, 0, 0);
        }
        for (int i = 0; i < nc; i++) {
            scanf(" (%d)%d", &u, &z);
            insert(u + 1, n + 1, z);
            insert(n + 1, u + 1, 0);
        }
        printf("%d\n", BFS());
    }
}