网络流简介

基本定义

网络（Network）在图论中指一个有向图 $G=(V,E)$ ，图上的每一条边都有一个值，叫做容量（Capacity），也有两个特殊点：源点（Source）和汇点（Sink）。

而对于一张网络 $G$ ，流（Flow）指的是一个函数 $f$ ， $f(u, v)$ 表示边 $u \to v$ 经过的流量，一个点 $u$ 的净流量可以表示为 $F(u) = \textstyle{\sum_{x \in V}} f(u, x) - \textstyle{\sum_{x \in V}} f(x, u)$ 。

每一张网络的流从源点 $st$ 出发，流向汇点 $ed$ ，对于流经的每一条边，都满足以下性质：

对于一条边 $u \to v$ 的容量 $c(u, v)$ ，始终有： $0 \le f(u, v) \le c(u, v)$ 。
对于除源汇点以外的任意一点，净流量均为 $0$ 。

由上述性质可知，源汇点的净流量均不为 $0$ ，并且 $\left | F(st) \right | = \left | F(ed) \right |$ ，我们不妨定义整张网络的流量为 $st$ 的净流量 $F(st)$ ，这便是网络流。

常见类型

最大流：对于网络 $G = (V, E)$ ，给每条边一定的流量，使得网络流尽可能大，此时 $F$ 为 $G$ 的最大流。
最小割：对于网络 $G = (V, E)$ ，找到 $st \cdot ed$ 的割 $\left \{ S, T \right \}$ ，使得其尽可能小，此时割 $\left \{ S, T \right \}$ 为 $G$ 的最小割。

对于网络 $G = (V,E)$ ，如果 $\left \{ S, T \right \}$ 是点集 $V$ 的划分（通俗说就是分为了两部分），即 $S \cup T = V$ 并且 $S \cap T = \varnothing$ 。如果满足 $st \in S,ed \in T$ ，我们称 $\left \{ S, T \right \}$ 是 $G$ 的一个割（Cut）。一个割具有容量，可以表示为： $\left \| S,T \right \| \gets \textstyle{\sum_{u \in S}} \textstyle{ \sum_{v \in T}} \ c(u, v)$ 。

最大流

讲解算法之前，先给出增广路（Augmenting Path）的定义：

对于边 $u \to v$ ，如果它的 $f(u, v) \lt c(u, v)$ ，就说明这条边有剩余容量，为 $c_f(u, v)$ 。一条增广路指从源点 $st$ 到汇点 $ed$ 的一条路径，所有经过的边都有剩余容量。

不难发现，仅当不存在增广路时，网络流才可能是最大的。

Ford-Fulkerson 算法

Ford-Fulkerson 算法（简称 FF 算法）并不是直接用来求解最大流的，而是寻找并更新增广路，从而求得。

如果单纯的贪心，会发现不同的更新顺序会导致不同的结果，然而确定次序十分复杂，FF 算法便是采取了反悔的方式：

建图时对于每条边 $u \to v$ 同时建立其反向边 $u \gets v$ ，只不过 $c(v, u) = c_f(v, u) \gets 0$ 。
每一次更新增广路时，如果边 $u \to v$ 流过 $\Delta f$ 的流量，使：

$c_f(u, v) \gets c_f(u, v) - \Delta f,c_f(v, u) \gets c_f(v, u) + \Delta f$

如上反复找到图中增广路并更新，直到不存在增广路为止。

像这样，通过推流操作带来的抵消效果使得我们在贪心的时候可以反悔，无需正确的选择也可以得到最优解。这就是 Ford–Fulkerson 算法的增广过程。

证明详见最大流 - OI Wiki (oi-wiki.org)。

Edmonds–Karp 算法

Edmonds–Karp 算法（简称 EK 算法）便是 FF 增广的典型应用。

算法过程

EK 算法运用 BFS 的方式，每一次遍历 $G$ 时，找到一条新的增广路，使用 FF 增广更新流 $f$ 以及相应的边，得到新的残余容量子图 $G'$ ，不断更新，直至增广路不存在。

时间复杂度分析

这似乎是一种最原始的暴力，时间复杂度似乎由于更新的次数难以保证。由于其证明难度极其复杂，这里不便赘述，详见最大流 - OI Wiki (oi-wiki.org)。增广总次数为 $O(|V| |E|)$ ，单次 BFS 增广的时间上界为 $O(| E |)$ ，因此总的时间复杂度为 $O(|V| |E|^2)$ 。

代码实现

bool bfs()
{
    memset(vis, 0, sizeof vis);
    hh = 0, tt = -1;
    dist[st] = INF, vis[st] = true;
    q[++ tt] = st;

    while (hh <= tt)
    {
        int ver = q[hh ++];
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i]; 
            if (vis[to] || !w[i]) continue;
            dist[to] = min(dist[ver], w[i]);
            pre[to] = i;
            q[++ tt] = to, vis[to] = true;
            if (to == ed) return true;
        }
    }
    return false;
}

void update()
{
    int cur = ed;
    while (cur != st)
    {
        int nxt = pre[cur];
        w[nxt] -= dist[ed], w[nxt ^ 1] += dist[ed];
        cur = e[nxt ^ 1];
    }
    ans += dist[ed];
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> st >> ed;
    while (m --)
    {
        int a, b, c; cin >> a >> b >> c;
        if (edge[a][b]) w[edge[a][b]] += c;
        else add(a, b, c), add(b, a, 0), edge[a][b] = idx - 1;
    }

    while (bfs()) update();
    cout << ans << '\n';

    return 0;
}

Dinic 算法

Dinic 算法与 EK 算法不同，但本质上都运用到了 FF 增广的思想。

算法过程

由于网络流只能单向传输，每条边只能从一边流经，我们以源点为起点建立与源点距离有关的分层图，从而忽略掉许多不可能增广的边。分层图可以通过 BFS 求得。

bool bfs()
{
    memset(vis, 0, sizeof vis);
    hh = 0, tt = -1;
    dist[st] = INF, vis[st] = true;
    q[++ tt] = st;

    while (hh <= tt)
    {
        int ver = q[hh ++];
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i]; 
            if (vis[to] || !w[i]) continue;
            dist[to] = min(dist[ver], w[i]);
            pre[to] = i;
            q[++ tt] = to, vis[to] = true;
            if (to == ed) return true;
        }
    }
    return false;
}

在求出的分层图上，不断的 DFS 求出剩余的增广路 $f'$ 并且并列到原来的流 $f$ 中，直到 BFS 时不存在从源点到汇点的增广路，此时的流 $f$ 便是最大流。

时间复杂度分析

通过一系列复杂的证明可知，单次 DFS 的时间复杂度为 $O(|V| |E|)$ ，分层图最多层数为 $O(|V|)$ ，因此 Dinic 算法的时间复杂度上界为 $O(|V|^2 |E|)$ 。

值得注意的是，如果整张图的容量均为 $1$ ，Dinic 算法的时间复杂度可以达到更优。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define DEBUG
#define x first
#define y second
#define File(a) freopen(a".in", "r", stdin); freopen(a".out", "w", stdout)

typedef long long LL;
typedef pair<int, int> PII;

const int N = 400, M = 10010;
const int INF = 0x3f3f3f3f;

int n, m, st, ed;
int cpy[N], h[N], e[M], ne[M], w[M], idx;
int dist[N], que[N], hh = 0, tt = -1;

inline void add(int a, int b, int c) { e[++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; }

bool bfs()
{
    memset(dist, 0, sizeof dist);
    hh = 0, tt = -1;
    dist[st] = 1, que[++ tt] = st;

    while (hh <= tt)
    {
        int ver = que[hh ++];
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (!dist[to] && w[i] > 0)
                dist[to] = dist[ver] + 1, que[++ tt] = to;
        }
    }
    return dist[ed];
}

int dfs(int ver, int flow)
{
    if (ver == ed || !flow) return flow;
    for (int &i = cpy[ver]; ~i; i = ne[i])
    {
        int to = e[i];
        if (dist[to] == dist[ver] + 1 && w[i] > 0)
        {
            int temp = dfs(to, min(flow, w[i]));
            if (temp > 0)
            {
                w[i] -= temp, w[i ^ 1] += temp;
                return temp;
            }
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, temp = 0;
    while (bfs())
    {
        memcpy(cpy, h, sizeof cpy);
        while (temp = dfs(st, INF))
            ans += temp;
    }
    return ans;
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(h, -1, sizeof h), idx = -1;
    cin >> n >> m >> st >> ed;
    while (m --)
    {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c), add(b, a, 0);
    }

    cout << dinic() << '\n';

    return 0;
}