网络流（network-flows）是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。
（2018.08.29 更新此文，你没有阅读过的船新版本）
网络流是信息学竞赛中的常见题型了。
网络流的定义
“网络流（network-flows）是一种类比水流的解决问题方法。”
假设现在有一张有限的有向图 G，这张图上有一个源点 $s$，一个汇点 $t$，每条边都有一个最大流量（即容量），就像复杂的水管网络。现在我们定义几个概念：
- 源点（Sources）：一切流量流入的点。
- 汇点（Sinks）：所有流量最终汇聚到的点。
- 容量（Capacity）：一条边的最大流量。
- 残量（Residual Capacity）：容量与流量之差。
网络流的三大基本性质
网络流任何时刻总满足以下三条性质：
1. 容量限制（Capacity Constraints）：$f(u,v)≤c(u,v)$，即一条边的流不能超过它的容量。（不然水管就要被挤爆了……）
2. 斜对称（Skew Symmetry）：$f(u,v)=-f(v,u)$，即由 $u$ 到 $v$ 的净流必须是由 $v$ 到 $u$ 的净流的相反。假设有 $x$ 的流量从 $u$ 流到 $v$，那么就相当于有 $-x$ 的流量从 $v$ 流到 $u$。
3. 流守恒（Flow Conservation）：对于除了源点 $s$ 和汇点 $t$ 以外的所有点，都满足：
\displaystyle \sum_{p\in G} f(p,u)= \sum_{q\in G} f(u,q)也就是说任何一个点的入流等于其出流，源点和汇点除外。
最大流问题
现在假设有无限的流量从源点 $s$ 流入，我们要求出最后流到汇点t的最大流量（注意任何时候上面三个条件都要满足）。
对于最大流问题可以用 Edmonds-Karp 算法或 Dinic 算法解决。后者是前者的优化，但是前者更易于理解，所以我们先了解 Edmonds-Karp 算法。
Edmonds-Karp 算法
Edmonds-Karp 算法（简称EK）的主要步骤如下：
- 找到一条源点到汇点的路径（其中每条边残量都要大于0）（这样的路径就是增广路（Augmenting Path）），并找出这条路径上每条边残量最小值 $min$；
- 将这条路径上每条边残量减去 min，将每条边的反向边加上 $min$（因为我们这条增广路是“随便找”的，不能保证解最优；将反向边加上 $min$ 相当于提供了“反悔”的机会），并将答案累计上 $min$；
- 重复以上过程，直到从 $s$ 到 $t$ 没有增广路为止。
（由于我太懒EK算法似乎在任何情况下都没有优化了的 Dinic 好，这里就不给出代码了……）
如何存储边
要快速又节省空间地求出一条边的反向边并不简单。这里我们可以用邻接表存储：在读取边的信息的同时，add(x,y,z)，add(y,x,0)，这样一条边与其相邻边的边号总是相邻。我们如果从0开始存储边号，那么i的相邻边就是i^1，就是它的反向边！（^表示异或）
Dinic 算法
Dinic 算法是对 Edmonds-Karp 的优化。
Edmonds-Karp 慢在哪里
因为 EK 算法中走到各个点没有一定的顺序，可以理解为“任意”的，所以会出现一定的问题。假设从 $s$ 有两条路径走到 $x$（假设 $x$ 是增广路上的一个点），假设这两条路径中最小的残量分别为 $min1$、$min2$，如果 $min2$ 更大，我们应该选择 $min2$ 这条路径，但是根据 EK 的处理方法我们会选择 $min1$，这样会导致重复处理。所以 EK 算法就会慢。
如何解决这个问题呢？Dinic 算法引入了“分层图”这个东西。
分层图
对于 $s$ 开始通过 BFS 构造分层图，这样可以保证日后 DFS 使用的从 $s$ 到达 $x$ 的路径都是“最短路”（也就是最优路径）。
Dinic 算法核心代码
inline bool BFS(){//这个函数的作用是构造分层图同时返回有无增广路
memset(deep,0,sizeof(deep));
deep[s]=1;//源点的深度为1
int head=0,tail=1;que[tail]=s;
while (head!=tail){
head++;
for (int i=lnk[que[head]];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[que[head]]+1,que[++tail]=son[i];
}
if (deep[t]==0) return 0;//如果汇点深度为0说明没有被修正到，也就是说没有增广路
return 1;
}
inline int DFS(int x,int now){//x为当前点，now为当前流量
if (x==t) return now;
for (int i=cur[x];i!=-1;i=cur[x]=nxt[i]) if (deep[son[i]]==deep[x]+1&&w[i]!=0){
int nxtd=DFS(son[i],min(now,w[i]));
if (nxtd>0){
w[i]-=nxtd;
w[i^1]+=nxtd;//反向边加
return nxtd;//向上传递
}
}
return 0;
}
inline void Dinic(){
while (BFS()){
for (int i=1;i<=n;i++) cur[i]=lnk[i];
while (int now=DFS(s,1<<30)) ans+=now;//初始流量为正无穷
}
}当前弧优化
Dinic 算法仍然可以优化，这个优化称为“当前弧优化”。基于这样一个事实：任何一条增广路中一条边不会存在两次。所以我们可以加一个数组 cur[x] 表示当前 $x$ 这个点循环到的边。（具体参见完整代码）
完整代码（含当前弧优化）
（洛谷模版题“最大网络流”（P3376）测评通过）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005,maxe=200005;
int n,m,s,t,tot=-1,ans=0,nxt[maxe],son[maxe],w[maxe],deep[maxn],lnk[maxn],que[maxn],cur[maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void add(int x,int y,int z){
tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline bool BFS(){//这个函数的作用是构造分层图同时返回有无增广路
memset(deep,0,sizeof(deep));
deep[s]=1;//源点的深度为1
int head=0,tail=1;que[tail]=s;
while (head!=tail){
head++;
for (int i=lnk[que[head]];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[que[head]]+1,que[++tail]=son[i];
}
if (deep[t]==0) return 0;//如果汇点深度为0说明没有被修正到，也就是说没有增广路
return 1;
}
inline int DFS(int x,int now){//x为当前点，now为当前流量
if (x==t) return now;
for (int i=cur[x];i!=-1;i=cur[x]=nxt[i]) if (deep[son[i]]==deep[x]+1&&w[i]!=0){
int nxtd=DFS(son[i],min(now,w[i]));
if (nxtd>0){
w[i]-=nxtd;
w[i^1]+=nxtd;//反向边加
return nxtd;//向上传递
}
}
return 0;
}
inline void Dinic(){
while (BFS()){
for (int i=1;i<=n;i++) cur[i]=lnk[i];
while (int now=DFS(s,1<<30)) ans+=now;//初始流量为正无穷
}
}
int main(){
memset(lnk,-1,sizeof(lnk));//因为边号从0开始存储，所以-1表示没有边
memset(nxt,-1,sizeof(nxt));
n=read();m=read();s=read();t=read();
for (int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
add(x,y,z);add(y,x,0);//构造反向边并且其边号与正向边相邻
}
Dinic();
printf("%d\n",ans);
return 0;
}模板题
参考
网络流_百度百科
网络流 - 维基百科，自由的百科全书
Dinic算法（研究总结，网络流）
网络流算法+例题整理 - CSDN博客
网络流【最大流&&最小割】——一篇简单易懂的博文
网络流和棒球赛淘汰问题 | Matrix67: The Aha Moments