网络流简介

基本定义

网络（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 算法运用 $\text{bfs}$ 的方式，每一次遍历 $G$ 时，找到一条新的增广路，使用 FF 增广更新流 $f$ 以及相应的边，得到新的残余容量子图 $G'$ ，不断更新，直至增广路不存在。

时间复杂度分析

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

代码实现

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

    while (hh <= tt)
    {
        int ver = que[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;
            que[++ 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), idx = -1;
    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 增广的思想。

算法过程

由于网络流只能单向传输，每条边只能从一边流经，我们以源点为起点建立与源点距离有关的分层图，从而忽略掉许多不可能增广的边。分层图可以通过 $\text{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;
}

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

时间复杂度分析

通过一系列复杂的证明可知，单次 $\text{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 res = 0, temp = 0;
    while (bfs())
    {
        memcpy(cpy, h, sizeof cpy);
        while (temp = dfs(st, INF)) res += temp;
    }
    return res;
}

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;
}

费用流

在网络流的基础上，每条边有另外的一个单位流量的费用 $f(u, v)$ 。

我们定义一条边上流经的费用为流量乘以单位流量的费用，即 $cost \gets f(u, v) \times c(u, v)$ 。整张网络的费用即为费用流，较为常见的问题有最小费用最大流，即在最大化 $\sum_{(u, v) \in E}c(u, v)$ 的前提下最小化 $\sum_{(u, v) \in E}f(u, v) \times c(u, v)$ 。

Successive Shortest Path 算法

同网络最大流的 FF 算法一样，最小费用最大流同样也有一种贪心的思路，叫做 SSP 算法。

算法过程

SSP 算法的核心思路即每次找到源点到汇点中单位费用最小的增广路进行增广，直到不存在为止。不难发现，这个贪心的思路在图上不存在单位费用为负的图的时候正确性是显而易见的，因此这个算法仅适用于单位费用为非负的网络流模型。

基于 EK 算法的实现

由于原始 EK 算法找到的是流经最少次数的流量，费用流要求的是单位费用最小的增广路，因此我们将 EK 算法中的 $\text{bfs}$ 函数改成 $\text{SPFA}$ 即可。

bool spfa()
{
    memset(dist, 0x3f, sizeof dist), memset(flow, 0, sizeof flow), hh = 0, tt = -1;
    dist[S] = 0, flow[S] = INF, que[++ tt] = S, inque[S] = true;

    while (hh <= tt)
    {
        int ver = que[hh ++];
        inque[ver] = false;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (!w[i] || dist[to] <= dist[ver] + f[i]) continue;
            dist[to] = dist[ver] + f[i], flow[to] = min(flow[ver], w[i]), pre[to] = i;
            if (!inque[to]) que[++ tt] = to, inque[to] = true;
        }
    }
    return flow[T] > 0;
}


void update()
{
    maxflow += flow[T];
    for (int ver = T; ver != S; ver = e[pre[ver] ^ 1])
    {
        w[pre[ver]] -= flow[T], w[pre[ver] ^ 1] += flow[T];
        mincost += flow[T] * f[pre[ver]];
    }
}

// while (spfa()) update();

基于 Dinic 算法的实现

类似 EK 算法，将 $\text{bfs}$ 转化为 $\text{SPFA}$ 即可，然而分层图应当依照费用进行分层，同时值得注意的是，在计算流量的 $\text{dfs}$ 中，每当遍历一个点就应该标记它不在接下来的搜索子树中搜到，即判断当前点是否重复加入至搜索队列当中。

详情看代码。

bool spfa()
{
    memset(dist, 0x3f, sizeof dist), hh = 0, tt = -1;
    que[++ tt] = S, inque[S] = true, dist[S] = 0;

    while (hh <= tt)
    {
        int ver = que[hh ++];
        inque[ver] = false;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (w[i] && dist[to] > dist[ver] + f[i])
            {
                dist[to] = dist[ver] + f[i];
                if (!inque[to]) que[++ tt] = to, inque[to] = true;
            }
        }
    }
    return dist[T] != INF;
}

int maxflow, mincost;

int dfs(int ver, int flow)
{
    if (ver == T || !flow) return flow;
    vis[ver] = true;    // !!!
    for (int &i = cpy[ver]; ~i; i = ne[i])
    {
        int to = e[i];
        if (!vis[to] && dist[to] == dist[ver] + f[i] && w[i] > 0)
        {
            int temp = dfs(to, min(flow, w[i]));
            if (temp > 0)
            {
                w[i] -= temp, w[i ^ 1] += temp, mincost += temp * f[i];
                return vis[ver] = false, temp;
            }
        }
    }
    return vis[ver] = 0;
}

void dinic()
{
    int temp = 0;
    while (spfa())
    {
        memcpy(cpy, h, sizeof cpy);
        while (temp = dfs(S, INF)) maxflow += temp;
    }
}