最大流与最小割

流网络

定义流网络 \(G = (\mathbf V, \mathbf E)\) 为一个有向图，其中 \(\mathbf V\) 为点集，\(\mathbf E\) 为边集。若 \((u, v) \in \mathbf E\)，有向边 \((u, v)\) 有一个容量 \(w(u, v)\)；若 \((u, v) \notin \mathbf E\)，定义 \(w(u, v) = 0\)。流网络有一个源点 \(s\)，汇点 \(t\)。

定义流 \(f\) 为流网络的一种状态，\(f(u, v)\) 为当前边 \((u, v)\) 上的流量，流满足两个限制：

容量限制：对于 \(u, v \in \mathbf V\)，\(0 \leq f(u, v) \leq w(u, v)\)。
流量守恒：对于 \(u \in \mathbf V \setminus \{s, t\}\)，\(\displaystyle\sum_{v \in \mathbf V} f(u, v) = \sum_{v \in \mathbf V} f(v, u)\)。

定义一个流的值 \(\mid f \mid = \displaystyle\sum_{v \in \mathbf V} f(s, v) - \sum_{v \in \mathbf V} f(v, s)\)，最大流问题要求值最大的一个 \(f\)。

残量网络

给定流网络 \(G\) 和流 \(f\)，定义残量网络 \(G_f\) 是由仍有空间对流量进行调节的边构成。定义残量网络 \(G_f\) 中的容量限制：

\[ w_f(u, v) = \begin{cases} w(u, v) - f(u, v), &(u, v) \in \mathbf E \\ f(v, u), &(v, u) \in \mathbf E \\ 0, &\text{otherwise} \\ \end{cases} \]

其中第二种情况为流网络 \(G\) 的反边，因为在增广的过程中只有增加一条边的流量的操作，而增广反边意味着缩减原边，能让残量网络对每条边上的流量缩减。

因为流网络 \(G\) 中，不存在互相反向的边，所以上面三种情况只能满足其一。

Tip

值得注意的是，若 \(w_f(u, v) = 0\)，我们认为残量网络中不存在边 \((u, v)\)。

增广路径

若残量网络 \(G_f\) 中存在源点 \(s\) 到汇点 \(t\) 的路径，则称这条路径为增广路径。设 \(\mathbf P\) 为增广路径 \(p\) 上边的集合，定义残存容量 \(w(p) = \displaystyle\min_{(u, v) \in \mathbf P} w_f(u, v)\)，增广路径上的每条边的流量都相同，且不大于 \(w(p)\)。

我们可以将增广路径看作一个流 \(f'\)（~~可以看出，~~\(f'\) 满足流的两个性质），这样，增广的过程可以看作原流和增广路径相加。因为增广路径从源点 \(s\) 出发，因此源点 \(s\) 的出度一定比入度大 \(1\)，根据 \(\mid f' \mid\) 的定义，\(0 \leq \mid f' \mid \leq w(p)\)。这样，\(\mid f + f' \mid = \mid f \mid + \mid f' \mid\)。我们希望结果流的值尽可能大，因此需要将 \(\mid f' \mid\) 取到上界，也就是 \(w(p)\)。这样可以看出走增广路径可以使流的值增大。

割

流网络 \(G = (\mathbf V, \mathbf E)\) 的一个切割 \((\mathbf S, \mathbf T)\) 将点集 \(\mathbf V\) 划分成 \(\mathbf S, \mathbf T\) 两个集合，且满足 \(\mathbf S \cup \mathbf T = \mathbf V, \mathbf S \cap \mathbf T = \varnothing, s \in \mathbf S, t \in \mathbf T\)。若流 \(f\) 是流网络 \(G\) 的一个流定义横跨切割 \((\mathbf S, \mathbf T)\) 的净流量 \(f(\mathbf S, \mathbf T)\)：

\[ \begin{aligned} f(\mathbf S, \mathbf T) = \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(u, v) - \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(v, u) \\ \end{aligned} \]

切割 \((\mathbf S, \mathbf T)\) 的容量 \(w(\mathbf S, \mathbf T)\)：

\[ \begin{aligned} w(\mathbf S, \mathbf T) = w(u, v) \\ \end{aligned} \]

一个流网络的最小割是网络中容量最小的切割。

结论

若流 \(f\) 为流网络 \(G\) 的一个流，则任何横跨该流的切割的净流量都是相同的，且等于 \(\mid f \mid\)。

证明

因为流量守恒，所以对任意 \(u \in \mathbf V \setminus \{s, t\}\)，有：

\[ \begin{aligned} \sum_{v \in \mathbf V} f(u, v) - \sum_{v \in \mathbf V} f(v, u) = 0 \\ \end{aligned} \]

根据 \(\mid f \mid\) 的定义，有：

\[ \begin{aligned} \mid f \mid &= \sum_{v \in \mathbf V} f(s, v) - \sum_{v \in \mathbf V} f(v, s) \\ &= \sum_{v \in \mathbf V} f(s, v) - \sum_{v \in \mathbf V} f(v, s) + \sum_{u \in \mathbf S \setminus \{s\}} \left[\sum_{v \in \mathbf V} f(u, v) - \sum_{v \in \mathbf V} f(v, u) \right] \\ &= \sum_{v \in \mathbf V} f(s, v) + \sum_{u \in \mathbf S \setminus \{s\}} \sum_{v \in \mathbf V} f(u, v) - \sum_{v \in \mathbf V} f(v, s) - \sum_{u \in \mathbf S \setminus \{s\}} \sum_{v \in \mathbf V} f(v, u) \\ &= \sum_{v \in \mathbf V} \left[f(s, v) + \sum_{u \in \mathbf S \setminus \{s\}} f(u, v) \right] - \sum_{v \in \mathbf V} \left[f(v, s) + \sum_{u \in \mathbf S \setminus \{s\}} f(v, u) \right] \\ &= \sum_{v \in \mathbf V} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf V} \sum_{u \in \mathbf S} f(v, u) \\ \end{aligned} \]

因为 \(\mathbf S \cup \mathbf T = \mathbf V, \mathbf S \cap \mathbf T = \varnothing\)，所以有：

\[ \begin{aligned} \mid f \mid &= \sum_{v \in \mathbf V} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf V} \sum_{u \in \mathbf S} f(v, u) \\ &= \sum_{v \in \mathbf S} \sum_{u \in \mathbf S} f(u, v) + \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf S} \sum_{u \in \mathbf S} f(v, u) - \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(v, u) \\ &= \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(v, u) - \left[\sum_{v \in \mathbf S} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf S} \sum_{u \in \mathbf S} f(v, u) \right] \\ \end{aligned} \]

因为后面中括号内的式子可以通过交换求和顺序转化为同一形式，因此两项相等，于是得到：

\[ \begin{aligned} \mid f \mid &= \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(u, v) - \sum_{v \in \mathbf T} \sum_{u \in \mathbf S} f(v, u) \\ &= f(\mathbf S, \mathbf T) \\ \end{aligned} \]

结论

流网络 \(G\) 中任意流的值不超过任意割的容量。

证明

\[ \begin{aligned} \mid f \mid &= \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(u, v) - \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(v, u) \\ &\leq \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(u, v) \\ &\leq \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} w(u, v) \\ &= w(\mathbf S, \mathbf T) \\ \end{aligned} \]

最大流最小割定理

若 \(f\) 为流网络 \(G\) 的一个流，则下面的条件等价：

流 \(f\) 是流网络 \(G\) 的一个最大流。
残量网络 \(G_f\) 没有增广路径。
\((\mathbf S, \mathbf T)\) 是流网络 \(G\) 的一个割，且满足 \(\mid f \mid = w(\mathbf S, \mathbf T)\)。

证明

\((1) \Rightarrow (2)\)：反证法。若流 \(f\) 是流网络 \(G\) 的一个最大流，且残量网络 \(G_f\) 有增广路径，上面已经证明了走增广路径会使流的值增大，因此流 \(f\) 不是最大流，与假设矛盾。

\((2) \Rightarrow (3)\)：若残量网络 \(G_f\) 没有增广路径，则残量网络 \(G_f\) 中不存在源点 \(s\) 到汇点 \(t\) 的路径。定义 \(u \rightarrow v\) 表示在残量网络 \(G_f\) 中存在 \(u\) 到 \(v\) 的路径，且路径不经过容量为 \(0\) 的边。令 \(\mathbf S = \{v \in \mathbf V : s \rightarrow v\}, \mathbf T = \mathbf V \setminus \mathbf S\)。可以看出，\((\mathbf S, \mathbf V)\) 是流网络 \(G\) 的一个割。根据刚才的定义，有：\(u \in \mathbf S, v \in \mathbf T, f(u, v) = w(u, v)\)（若 \(f(u, v) \ne w(u, v)\)，则此时残量网络上存在边 \((u, v), s \rightarrow v\)，与 \(\mathbf S\) 的定义矛盾），\(u \in \mathbf T, v \in \mathbf S, f(u, v) = 0\)（若 \(f(u, v) \ne 0\)，残量网络中存在反边 \((v, u), u \rightarrow s\)，与 \(\mathbf S\) 的定义矛盾）。因此有：

\[ \begin{aligned} \mid f \mid = f(\mathbf S, \mathbf T) = \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(u, v) - \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(v, u) = \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} w(u, v) = w(\mathbf S, \mathbf T) \\ \end{aligned} \]

此时，\((\mathbf S, \mathbf T)\) 是流网络 \(G\) 的最小割。

\((3) \Rightarrow (1)\)：因为 \(\mid f \mid \leq w(\mathbf S, \mathbf T)\)，而此时 \(\mid f \mid\) 已经取到上限，因此流 \(f\) 是流网络 \(G\) 的最大流。

残量网络中不加反边的不正确性

对于流网络 \(G\) 的一个切割 \(f\)，定义其不正确的残量网络 \(G_f'\)：

\[ w_f(u, v) = \begin{cases} w(u, v) - f(u, v), &(u, v) \in \mathbf E \\ 0, &\text{otherwise} \\ \end{cases} \]

因为在证明横跨流 \(f\) 的切割的净流量时没有用到残量网络，所以结论依然成立，即 \(\mid f \mid = f(\mathbf S, \mathbf T)\)。

在证明上面 \((2) \Rightarrow (3)\) 时，我们令 \(\mathbf S = \{v \in \mathbf V : s \rightarrow v\}, \mathbf T = \mathbf V \setminus \mathbf S\)。若原图中存在边 \((v, u), u \in \mathbf S, v \in \mathbf T\) 而不存在边 \((u, v)\)，此时可能存在 \(f(v, u) > 0\) 的情况（因为不正确的残量网络中始终不存在反边 \((u, v)\)，而正确的残量网络中因为反边的存在而不存在这种情况）。根据上面的结论 \(\mid f \mid = f(\mathbf S, \mathbf T) = \displaystyle\sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(u, v) - \sum_{u \in \mathbf S} \sum_{v \in \mathbf T} f(v, u)\)，后面的一项可能大于 \(0\)，因此 \(\mid f \mid\) 可能小于最小割，不是最大流。

EK 算法

使用 BFS 寻找增广路径，并更新，直到残量网络 \(G_f\) 没有增广路径，时间复杂度 \(O(\mid \mathbf V \mid \mid \mathbf E \mid^2)\)。

Bug

当前内容待完善。

Dinic 算法

我们可以一次 DFS 寻找到多条增广路径。首先对残量网络 \(G_f\) 进行一遍 BFS，处理出每个点距源点 \(s\) 的最短距离，并强制 DFS 每次只能往比当前结点距离多 \(1\) 的结点走（即只能沿最短路增广）。这样避免了往回走并无限递归的情况发生。一直增广直至残量网络中源点和汇点不连通。

正确性证明

证明

当增广结束时，源点和汇点不连通，即残量网络中无增广路径，由最大流最小割定理，此时求出的是最大流。

代码

#include <cstring>
#include <iostream>
#include <queue>
#define TO(x) edge[x].to
#define W(x) edge[x].w
#define NXT(x) edge[x].nxt
using namespace std;
typedef long long ll;
const int MAXN1 = 205, MAXN2 = 5005;
const ll INF = 1ll << 50;
int n, m, s, t;
class Graph {
private:
    struct Edge {
        int to, w, nxt;
        Edge() {}
        Edge(int to, int w, int nxt) : to(to), w(w), nxt(nxt) {}
    };
    int tot, cur[MAXN1], dep[MAXN1], head[MAXN1];
    Edge edge[MAXN2 << 1];
    bool bfs() {
        memset(dep, 0, sizeof(dep)), memcpy(cur, head, sizeof(cur));
        queue<int> q;
        for (dep[s] = 1, q.emplace(s); !q.empty(); q.pop())
            for (int e = head[q.front()]; e; e = NXT(e))
                if (W(e) && !dep[TO(e)]) {
                    dep[TO(e)] = dep[q.front()] + 1, q.emplace(TO(e));
                    if (TO(e) == t)
                        return true;
                }
        return false;
    }
    ll dfs(int x, ll flow) {
        if (x == t)
            return flow;
        ll now = flow;
        for (int &e = cur[x]; e; e = NXT(e))
            if (W(e) && dep[TO(e)] == dep[x] + 1) {
                int f = dfs(TO(e), min(now, 1ll * W(e)));
                W(e) -= f, W(e ^ 1) += f, now -= f;
                if (!now)
                    break;
            }
        return flow - now;
    }

public:
    Graph() { tot = 1; }
    void addEdge(int u, int v, int w) {
        edge[++tot] = Edge(v, w, head[u]), head[u] = tot;
        edge[++tot] = Edge(u, 0, head[v]), head[v] = tot;
    }
    ll solve() {
        ll ans = 0;
        while (bfs())
            ans += dfs(s, INF);
        return ans;
    }
} graph;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 1, u, v, w; i <= m; ++i)
        cin >> u >> v >> w, graph.addEdge(u, v, w);
    cout << graph.solve() << "\n";
}

一些细节

Tip

dep 记录结点所在层，cur 记录当前弧。dfs 中的 flow 记录残量网络中 \(s \rightarrow x\) 的最大流量，now 记录增广后 \(s \rightarrow x\) 剩余流量。
连边时，对于同一条边，令原图中的边的编号为 \(2x\)，反边的编号为 \(2x + 1\)，这样原边和反边的编号正好是 \(\operatorname{xor} 1\) 的关系，方便处理。edge 数组实际存的是残量网络中的边。
每次 BFS 时，需要清空 dep 数组、队列（因为如果遇到了终点就会直接返回而不是继续循环直到队列空，所以下次 BFS 开始时队列不一定空）以及重置 cur 数组，还需将 dep[s] 赋为 \(1\)（因为可能有流入 \(s\) 的边，而如果不赋值，就会认为 \(s\) 未到达过，并把 \(s\) 分到一个奇怪的层中）。

当前弧优化

注意这段 DFS 代码：

ll dfs(int x, ll flow) {
    if (x == t)
        return flow;
    ll now = flow;
    for (int &e = cur[x]; e; e = NXT(e))
        if (W(e) && dep[TO(e)] == dep[x] + 1) {
            int f = dfs(TO(e), min(now, 1ll * W(e)));
            W(e) -= f, W(e ^ 1) += f, now -= f;
            if (!now)
                break;
        }
    return flow - now;
}

代码中的 cur 数组记录的是当前弧。更新 cur 的操作只有在两种情况下会发生（令 \(v\) 为当前边的终点）：

在遍历 \(x\) 的出边时，若这条边的权值为 \(0\) 或 \(v\) 不在 \(x\) 的下一层，则这条边不可能成为增广路径的一部分，于是跳过。
\(v\) 在 \(x\) 的下一层，且边权大于 \(0\)，于是继续 dfs，并返回这条增广路径的残存容量。这时可能出现两种情况，即 \(s \rightarrow x\) 无法继续增广（代码中 now 等于 \(0\)），此时 \(to \rightarrow t\) 可能可以继续增广；或 \(s \rightarrow x\) 可以继续增广，而 \(to \rightarrow t\) 无法继续增广（代码中 now 大于 \(0\)）。如果是其中的第一种，也就直接返回当前答案而不更新 cur；如果是第二种，\(to \rightarrow t\) 无法继续增广，也就没必要枚举，于是改变 cur 的值。

在实现时，可以选择枚举 cur 的引用，这样使用邻接表遍历边的时候会更新 cur。同时，DFS 下一个结点后应先判断 now 的值（单独使用 if 语句，而不是在循环条件中判断），如果为 \(0\) 则直接返回，才能不更新 cur（如果更新会变慢很多）。

时间复杂度

\(O(\mid \mathbf V \mid ^2 \mid \mathbf E \mid)\)。

Bug

当前内容待完善。

动态建图

在不需要删边而只需要加边的情况下，如果需要对加边的每一阶段的最大流，可以使用动态建图的技巧。由于 Dinic 算法存的实际上是残量网络的边，当新加边时，可能再次使源点和汇点连通。此时若再求一遍最大流，相当于又增广了几条路径，因此原图中的最大流为之前求出的所有最大流之和。

最小割

根据最大流最小割定理，图中两点的最小割可以转化为网络流中两点的最大流。

Warning

求无向图的最小割时，原图中的一条无向边需要在流网络中连两条有向边。