欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-11 08:19:17
题目链接 本篇博客延续上篇博客(最大流Dinic算法)的内容,此次使用EK算法解决最大流问题。 EK算法思想:在图中搜索一条从源点到汇点的扩展路,需要记录这条路径,将这条路径的最大可行流量 liu 增加到结果ans中,然后反向从汇点到源点更新这条路径上的每条边的权值(减去此次的liu),同时反向边的 ......

 

本篇博客延续(最大流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());
    }
}