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

本篇博客延续上篇博客（最大流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 = ;

const int MAXN = 0x3fffffff;

struct Edge {

    int to;

    int value;

    int next;

}e[ * 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, -, sizeof(head));

    cnt = -;

}

int BFS() {

    int ans = ;

    while ()

    {

        memset(p, -, sizeof(p));

        queue<int> Q;

        Q.push();

        p[] = MAXN;

        while (!Q.empty()) {

            int u = Q.front();

            Q.pop();

            for (int edge = head[u]; edge != -; edge = e[edge].next) {

                int v = e[edge].to;

                if (p[v] ==- && e[edge].value > ) {

                    p[v] = min(p[u], e[edge].value);

                    fa[v] = u;

                    edgeIndex[v] = edge;

                    Q.push(v);

                    if (v == n + ) goto endw;

                }

            }

        }

    endw:;

        if (p[n+] == -) return ans;

        else {

            ans += p[n + ];

            int x = n + ;

            while (x) {

                int edge = edgeIndex[x];

                e[edge].value -= p[n + ];

                e[edge ^ ].value += p[n + ];

                x = fa[x];

            }

        }

    }

}

int main()

{

    while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) {

        init();

        int u, v, z;

        for (int i = ; i < m; i++) {

            scanf(" (%d,%d)%d", &u, &v, &z);

            insert(u + , v + , z);

            insert(v + , u + , );

        }

        for (int i = ; i < np; i++) {

            scanf(" (%d)%d", &u, &z);

            insert(, u + , z);

            insert(u + , , );

        }

        for (int i = ; i < nc; i++) {

            scanf(" (%d)%d", &u, &z);

            insert(u + , n + , z);

            insert(n + , u + , );

        }

        printf("%d\n", BFS());

    }

}

巴特西

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

最新文章

热门文章