简介

EK 算法，即 Edmonds-Karp 动能算法，是求解最大流的基本算法。

反向边

反向边 是帮助程序能发现更优解。

例子

例：

发现了一条 \(* \rightarrow A \rightarrow B \rightarrow *\) 的 增广路。

但后面发现分成两条：

\(* \rightarrow C \rightarrow B \rightarrow *\)

\(* \rightarrow A \rightarrow D \rightarrow *\)

这样比原方案更优。

所以要建立一条 反向边，\(B \rightarrow A\)，让流过去的水能够流回来。

建立反向边

链式前向星（链表）

在添加 正向边 时，也把 反向边 给添加（容量为0）。

这样对于第 i 条边的 反向边 是 \(i\oplus 1\)（编号请从偶数开始存）

邻接矩阵

易。

过程

整体来说，\(EK\) 就是一个不断 BFS 和 增广 的过程。

下文中，\(S\) 指源点，\(T\) 指汇点，\(c_i\) 指边可通过的容量，\(l_i\) 指点 \(i\) 的流量。

BFS

每次从源点出发，进行搜索，若寻找到 \(T\)，结束 BFS 进行增广。

假设现在我们要从 \(x \rightarrow u\)：

  1. 先判断是否能到达 \(u\)，即 \(u\) 是第一次到达且边的可通过的容量大于 \(0\)。
  2. 更新 \(l_u=min(l_x,c_i)\)。
  3. 记录这条边，最后要反跑找到的路径以更新容量，注意，此时不能直接更新流量，因为不确定该增广路的最大可流流量。
  4. 遇到 \(T\) 后，跳出 BFS，即找到任意一条增广路就跳出。

增广

反跑增广路。

此时 \(l_t\) 即为该增广路的最大可流流量。

所以正向边的可通过容量 \(-l_t\)，即反向边的可通过容量 \(+l_t\)。

答案显然也 \(+l_t\)。

就这样不断 BFS 和 增广，直到跑不到 \(T\)。

时间复杂度：\(O(nm^2)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int N = 2e5 + 5, M = 2e6 + 5; // 点数，边数

constexpr ll LLINF = 1e18;

struct Graph {
    struct Edge {
        int v, nt;
        ll c; // 可通过流量
    } e[M << 1];
    int hd[N], tot = 1; // 注意从 2 开始对边编号
    void add(int u, int v, ll c) { e[++tot] = {v, hd[u], c}, hd[u] = tot; }
    void uadd(int u, int v, ll c) { add(u, v, c), add(v, u, 0); }
} g;

namespace EK {
int S, T;             // 源点，汇点
int prep[N], pree[N]; // 前驱点，前驱边
ll l[N];
ll flow() {
    ll res = 0;
    while (true) {
        queue<int> q;
        vector<int> ph;
        q.push(S);
        l[S] = LLINF;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), ph.push_back(u);
            for (int i = g.hd[u]; i; i = g.e[i].nt) {
                int v = g.e[i].v;
                if (!l[v] && g.e[i].c) {
                    prep[v] = u, pree[v] = i;
                    l[v] = min(l[u], g.e[i].c);
                    q.push(v);
                }
            }
            if (l[T]) break;
        }
        if (!l[T]) break;

        for (int u : ph) l[u] = 0; // 重置边的流量

        for (int u = T; u != S; u = prep[u]) {
            int i = pree[u];
            g.e[i].c -= l[T], g.e[i ^ 1].c += l[T];
        }
        res += l[T];
    }
    return res;
}
} // namespace EK

int n, m;

int main() {
    cin >> n >> m >> EK::S >> EK::T;

    for (int i = 1, u, v, c; i <= m; i++) {
        cin >> u >> v >> c;
        g.uadd(u, v, c);
    }

    cout << EK::flow() << endl;

    return 0;
}

参考：oi-wiki