网络流最大流算法总结（Edmonds-Karp 算法 + Dinic 算法）

This blog post is only available in Simplified Chinse.

网络流（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;
}

模板题

洛谷3376 POJ1273

参考

网络流_百度百科网络流 - 维基百科，自由的百科全书 Dinic算法（研究总结，网络流）网络流算法+例题整理 - CSDN博客网络流【最大流&&最小割】——一篇简单易懂的博文网络流和棒球赛淘汰问题 | Matrix67: The Aha Moments

3/25/2018