跳转至

最大流

定义ψ(｀∇´)ψ

因为大部分是看 youtube 上的视频学的所以标注了一些英文名词。

  • 网络（Flow Network）：网络是一个有向图 \(G = (V,E)\)，并且对于 \(\forall (u,v) \in E\)，有一个权值 \(c(u, v)\)，称为边 \((u, v)\) 的容量（Capacity）。
  • 源点（Source）：\(S \in V\)
  • 汇点（Sink）：\(T \in V \land S \not= T\)
  • 流（Flow）：也可以说是一个流函数 \(f(u, v)\)，其满足以下条件：
    • \(f(u, v)\) 是一个定义在二元组 \((u \in V, v\in V)\) 的实数函数。
    • \(f(u, v)\) 不大于 \(c(u, v)\)，也被称作容量限制。
    • \(f(u, v) = -f(v, u)\)，也被称作斜对称性质。
    • \(\forall x \in V - \{S, T\}\Rightarrow\sum\limits_{(u, x) \in E}^{}f(u, x) = \sum\limits_{(x, v) \in E}^{}f(x, v)\)，也被叫做流量守恒。
    • 其实你可以把边看作水管，点看作水站，流量看作水，就很好理解了。
  • 网络的流量：\(\sum\limits_{(S, v) \in E}^{}f(S,v)\)。因为流量守恒显然也等于 \(\sum\limits_{(u, T) \in E}^{}f(u, T)\)。
  • 剩余容量（Residual Capacity）：\(c_f(u, v) = c(u, v) - f(u, v)\)，可以理解为，有 \(f(u, v)\) 这么多水同时流入之后，最多还能同时流入多少。
  • 残量网络（Residual Network）：对于一个 \(G\) 上的流 \(f\)，定义残量网络 \(G_f\) 为：\(G_f = (V, E_f), E_f = \{(u, v) | c_f(u, v) > 0\}\)，也就是还能继续加水的边和 \(G\) 中所有节点构成的一张图。

最大流ψ(｀∇´)ψ

最大流问题，简单来说就是让我们在网络 \(G\) 上求出一个恰当的流 \(f\)，使得 \(G\) 的流量最大。

Ford-Fulkerson Augmentψ(｀∇´)ψ

这是一个很神奇的算法。

我们定义 \(G_f\) 上的一条增广路（Augment Path）为一条 \(S \to T\) 的路径 \(P\)。

可以注意到，如果我们给一条增广路上的所有边的流量加上一个值 \(d = \min\{c_f(u, v)\}, (u, v) \in P\)，就能够增加整个网络的流量，这个值也被称作增广路的瓶颈（Bottleneck）。

这个过程被称作增广，可以发现，如果我们不断进行增广并更新 \(f, G_f\)，直到不存在增广路，此时的 \(f\) 就一定是最大流。

但是仍然存在一个问题，按照 \(f\) 的定义，对于一条边 \((u, v)\)，如果 \(f(u,v) \gets f(u, v) + d\)，那么根据斜对称性，应当有 \(f(v, u) \gets f(v, u) - d\)。

如果我们忽略这个过程，那么求解出的 \(f\) 就是不正确的，这个过程被称作退流。

当然 \(f\) 可能为负数，这不要紧，可以看作我们把管子撑开了一点，它的“额定”容量是没变的，不过能装的水变多了，仅此而已。

我们还需要关心的一个问题是，我们选择增广路的顺序，可能会决定 \(f\) 是否是最优的。

比如有两条增广路 \(P_1,P_2\)，并且存在一个 \(u \in P_1, P_2\)。

有很大概率是，如果先选择 \(P_1\)，我们用完了 \(u\) 流进来的流量，但是如果我们先选 \(P_2\)，可能前面流过来的更多，然后能出去的就更多，我们求出的流就不优了。

比如这个例子（OI-wiki 的）

假设容量都是 \(1\)，可以发现如果我们先考虑 I 中的增广路话，\(u\) 的流量就用完了，这个局部网络的流量为 \(1\)。

如果先考虑 II 中的增广路，那么网络的流量是 \(2\)。

这就出现了问题，但是如果像 III 一样做一次退流，那么因为反向边的存在，可以发现，虽然我们考虑了 I 中的增广路，但是它对 II 中的增广路实际上没有影响。

也就是说，退流操作告诉我们：不必顾虑选错顺序，使劲增广就完事儿了，出事儿了有退流操作顶着！

max-flow-1.png

那么有了这些理论基础，我们就要考虑怎么实现了。

具体来说，我们应当怎么不断找到增广路进行增广和退流？

Dinic's Algorithmψ(｀∇´)ψ

我不知道怎么解释这个算法的来源（怎么想到的），所以直接叙述步骤了：

  1. 对当前的 \(G_f\) 使用 BFS 构造一张层次图（Level Graph） \(G_L = (V, E_L), E_L = \{(u, v) | dep(u) + 1 = dep(v), (u, v) \in E_f\}\)，其中 \(dep\) 为 bfs 时记下的层数（Level）。
  2. 使用 DFS 求出 \(G_L\) 上的一个阻塞流（Blocking Flow）\(f_b\)，其中 \(f_b\) 为 \(G_L\) 上的一个增广流（也就是说这个流描述了我们给哪些边添加了多少流量），使得我们使用 \(f_b\) 对 \(G_L\) 增广之后，\(G_L\) 上不再存在增广路（增广路都被“阻塞”了）
  3. 令 \(f \gets f + f_b\)，也就是把阻塞流并到原来求出的 \(f\) 中。
  4. 重复 1~3 直到 \(G_f\) 上不存在增广路，此时的 \(f\) 为最大流。

正确性是显然的，不过还有一个问题。

在我们求阻塞流的时候，如果存在一个 \(u\) 有大量的出边和入边，那么每次我们通过别的节点 dfs 走入边流入 \(u\) 的时候，都需要扫描所有的入边并 DFS。

很显然这是极度浪费的，会使得增广的次数达到 \(O(|E|^2)\) 级别。

可以注意到我们这里是在 DFS，也就是说，其实我们如果进行了一次 DFS(\(v\))，并递归回来，无非就两种情况：

  1. 最后走到 \(T\) 求出了阻塞流
  2. 被之前已经求出的阻塞流挡住了，遇到了“死角”（Dead Ends）。

所以只要我们进入了 \(v\)，下次再进入 \(v\) 都是在浪费时间，所以我们不妨剪枝，记录一个 \(cur(u)\) 表示当前第一条还需要 DFS 的边的编号。

这里主流的有两种实现，一种是 int &i = cur[u]；一种是 i = cur[u];，在 for 里面 cur[u] = i。

据 Ultimadow 说，好像 int &i = cur[u] 会把没流完的边 skip，巨大多轮 BFS 之后才能访问回来，所以这个写法假了（）

这个操作被称为“当前弧优化”，是保证 Dinic 时间复杂度的最重要一环。

不过有的时候不加也没什么事情，要看图的性质和结构（）

可以看一下这个过程（截取自 WilliamFiset 的视频 Dinic's Algorithm | Network Flow | Graph Theory）：

Dinic.mp4

还有一个优化叫做多路增广，思想大概就是只要有剩余容量就使劲增广直到不能增广。

这就只是一个常数小优化罢了。

时间复杂度分析暂时咕咕咕了，之后再来。

代码实现：

Code 
 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
72
73
74
75
76
77
78
79
80
// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long 

using namespace std;
using i64 = long long;

const int si = 5e3 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, m, S, T;
int tot = 0, head[si], cur[si];
struct Edge { int ver, Next, cap, flow; } e[si << 1];
inline void add(int u, int v, int w) { e[tot] = (Edge){v, head[u], w, 0}, head[u] = tot++; }

int dep[si];
bool Bfs() {
    std::queue<int> q;
    memset(dep, 0, sizeof dep);
    dep[S] = 1, q.push(S);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = e[i].Next) {
            int v = e[i].ver;
            if(!dep[v] && e[i].cap - e[i].flow > 0)
                dep[v] = dep[u] + 1, q.push(v);
        }
    }
    return dep[T] > 0; // 是否存在增广路
}
// minRest: 增广路上最小的剩余容量
int Dfs(int u, int minRest) {
    if(u == T || minRest == 0) 
        return minRest;
    int rest = 0;
    for(int i = cur[u]; ~i; i = e[i].Next) {
        cur[u] = i; int v = e[i].ver;
        if(dep[u] + 1 != dep[v]) continue;
        int d = Dfs(v, min(minRest - rest, e[i].cap - e[i].flow));
        rest += d, e[i].flow += d, e[i ^ 1].flow -= d;
        if(rest == minRest) return rest; 
    }
    return rest;
}

int Dinic() {
    int maxFlow = 0;
    while(Bfs()) {
        memcpy(cur, head, sizeof(int) * (n + 1));
        maxFlow += Dfs(S, inf);
    }
    return maxFlow;
}

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(head, -1, sizeof head);  

    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, 0); // 反向边初始容量为 0
    }
    cout << Dinic() << endl;

    return 0;
}
最后更新: July 10, 2023