网络流简介

容量网络

网络：指一个有向图 $G(V,E)$.

容量：在 $G$ 中，称每条边 $(u, v)$ 的权值 $c(u, v)$，为这条边的容量；特殊的，若 $(u,v)\notin E$，$c(u, v)=0$.

源点和汇点：$V$ 中的两个特殊点。一般记 $s$ 为源点，$t$ 为汇点，$s\neq t$.

流

流函数

网络 $G$ 的流函数是定义在二元组( $u\in V, v\in V$ )上的实数函数 $f(u, v)$.

$$
f(u,v)=
\left\{
\begin{aligned}
&f(u,v),&(u,v)\in E\\
&-f(v,u),&(v,u)\in E\\
&0,&(u,v)\notin E,(v,u)\notin E
\end{aligned}
\right.
$$

定义

对于 $(u, v)\in E$，$f(u, v)$ 称为边的流量，$c(u, v)-f(u, v)$ 称为边的剩余流量。

整个网络的流量为 $\sum_{(s, v)\in E} f(s, v)$，也就是从源点出发的所有流量的和。

性质

$f(u, v)$ 满足以下三条性质：

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 $f(u,v)\leq c(u,v)$;
斜对称性：每条边的流量与其相反边的流量之和为 $0$，即 $f(u,v)=-f(v,u)$;
流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V\setminus\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$.

最大流

概述

在一个流量网络中，求从源点 $s$ 流向汇点 $t$ 的最大流量。流量定义为：从源点出发的所有流量的和。

Ford-Fulkerson 增广路算法

通过寻找增广路来更新最大流。注意：这里的增广路与二分图中的增广路定义不同。

残量网络

残量：给定容量网络 $G(V, E)$ 及可行流 $f$，$(u, v)$ 上的残量记为 $c_f(u, v)=c(u, v)-f(u, v)$.

对于每条边而言，残量为这条边可以增加的容量。

残量网络：对于容量网络 $G(V, E)$ 及其上的网络流 $f$，$G$ 关于 $f$ 的残量网络为 $G_f(V_f, E_f)$. $(u, v)\in E_f$ 的边权记为 $c_f(u, v)$ . 残量网络 $G_f$ 满足：

$V_f=V$
对于任意 $(u, v)\in E$，如果 $f(u, v) < c(u, v)$，那么 $(u, v)\in E_f$ 且 $c_f(u, v) = c(u, v) – f(u, v)$.
对于任意 $(u, v)\in E$，如果 $f(u, v) > 0 $，那么 $(v, u)\in E_f$ 且 $c_f(v, u)=f(u, v)$.

通俗的来说，比如对于一条边 $(u, v)$，$f(u, v)=3$，$c(u, v)=5$。这条边的流量最多可以再增加 $2$，所以残量网络中 $c_f(u, v)=2$；同时，这条边的流量最多可以减少 $3$，又因为 $v$ 向 $u$ 增加流量，等价于 $u$ 向 $v$ 减少流量，所以在残量网路中的体现就是 $c_f(v, u)=3$。

因此，残量大于 $0$ 的边有可能不在原图 $G$ 中（但这条边的反向边在原图 $G$ 中）。

增广路

在原图 $G$ 中，若一条从源点到汇点的路径满足：路径上所有边的剩余容量都大于 $0$，那么这条路被称为增广路。

或者说，在残量网络 $G_f$ 中，能找到的从源点到汇点的路径，都是增广路。

EK算法——Edmond-Karp动能算法

思想

BFS在残量网络上找增广路，只要能找到一条增广路，就一定能对其进行增广。

方法

比如我们在残量网络找到了一条路径，计算出路径上所有边中的最小剩余流量 $rest$，将所有边的剩余流量减去 $rest$ 显然满足条件，于是流量增加了。

时间复杂度为 $\mathcal{O}(nm^2)$，$n$ 为点数，$m$ 为边数。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200;
const int MAX_M = 400;
const int INF = 0x3f3f3f3f;
struct edge {
    int u, v, c, next;
} edge[MAX_M];
int head[MAX_N], eid, S, T;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    edge[eid].u = u;
    edge[eid].v = v;
    edge[eid].c = c;
    edge[eid].next = head[u];
    head[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int pre[MAX_N]; // pre[u]记录节点u通过哪条边到达，记录的是边的下标
void bfs() {
    queue<int> q;
    q.push(S);
    memset(pre, -1, sizeof(pre));
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].v;
            if(pre[v] == -1 && edge[i].c) {
                pre[v] = i;
                if(v == T) {
                    break;
                }
                q.push(v);
            }
        }
        if(pre[T] != -1) {
            break;
        }

    }
}
int EK() {
    int ret = 0;
    while(1) {
        bfs();
        if(pre[T] == -1) {
            break;
        }
        int Min = INF;
        for(int u = T; u != S; u = edge[pre[u]].u) {
            Min = min(Min, edge[pre[u]].c);
        }
        for(int u = T; u != S; u = edge[pre[u]].u) {
            edge[pre[u]].c -= Min;
            edge[pre[u] ^ 1].c += Min;
        }
        ret += Min;
    }
    return ret;
}
int main() {
    int n, m;
    init();
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v, flow;
        cin >> u >> v >> flow;
        addedge(u, v, flow);
    }
    cin >> S >> T;
    cout << EK() << endl;
    return 0;
}

Dinic算法

思想

建立层次网络。对图上的点进行分级，以距离源点的最近距离的大小关系作为等级（等级从小到大，等价于距离源点的距离按升序排序）。增广的时候流量只会从低级节点走向高级节点，不会像EK算法一样出现往回走的情况。

建图方法：从源点开始BFS一遍即可。

建图之后，通过DFS找增广路。每次找增广路时的方法是多路增广。多路增广是说：每次找到一条增广路的时候，我们可以用残余的部分流量，再找出一条增广路。这样有一些边就可以少被经过一次，能够提高算法效率。

每次DFS之后再重新BFS一遍，直到图中没有增广路存在，也就是汇点不再在层次网络当中。

算法极限时间复杂度是 $\mathcal{O}(n^2m)$，与EK算法相同，但在稀疏图中远达不到这个复杂度。

优化——当前弧优化

如果一条边已经被增广过，那么它就没有再被增广第二次的可能性。因为只要在DFS中遍历到过这条边，那么经过这条边能引出的所有增广路都被增广过了，这条边不可能再被增广了。

这是一个很强的优化，能让Dinic算法跑的飞快。

实例

来自计蒜客Level 6课程。https://www.jisuanke.com/course/4728/287305

TODO.

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, c, fail;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    e[eid].v = v;
    e[eid].fail = p[u];
    e[eid].c = c;
    p[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = p[u]; i != -1; i = e[i].fail) {
            int v = e[i].v;
            if(e[i].c > 0 && d[v] == -1) {
                q.push(v);
                d[v] = d[u] + 1;
            }
        }
    }
    return (d[T] != -1);
}
int dfs(int u, int flow) {
    if(u == T) {
        return flow;
    }
    int res = 0;
    for(int i = p[u]; i != -1; i = e[i].fail) {
        int v = e[i].v;
        if(e[i].c > 0 && d[u] + 1 == d[v]) {
            int tmp = dfs(v, min(flow, e[i].c));
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i ^ 1].c += tmp;
            if(flow == 0) {
                break;
            }
        }
    }
    if(res == 0) {
        d[u] = -1;
    }
    return res;
}
int Dinic() {
    int res = 0;
    while(bfs()) {
        res += dfs(S, INF);
    }
    return res;
}
int main() {
    int n, m;
    init();
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v, flow;
        cin >> u >> v >> flow;
        addedge(u, v, flow);
    }
    cin >> S >> T;
    cout << Dinic() << endl;
    return 0;
}

参考资料

网络流简介 – OI Wiki

网络流 – 计蒜客 Level 6 课程