网络流学习笔记

#0 一些定义

对于带权有向图 $G$：

• 定义 $(x\to y,w)$ 为一条权值为 $w$ 的从 $x$ 连向 $y$ 的有向边；
• 定义 $V(G)$ 为图 $G$ 的点集，$E(G)$ 为 $G$ 的边集；

#1 什么是网络流

定义 1.1（网络、源点汇点、容量）

定义网络 $(G,S,T)$ 如下：

• $G$ 是一个边带非负权的有向图，$S$ 和 $T$ 是 $G$ 中的节点；
• $S$ 被称为源点，$T$ 被称为汇点；
• 对于 $G$ 中的边 $(x\to y,w)$，$w$ 被称为改边的容量；

定义 1.2（流、流量）

对于一个网络 $(G,S,T)$，定义一组流 $F=f_{[1,|E(G)|]}$，其中 $f_i$ 为第 $i$ 条边被使用的流量，需要满足：

• $\forall 1\le i\le|E(G)|$，有 $f_i\le w_i$；
• $\forall u\in V(G),u\notin\{S,T\}$，有 $\sum\limits_{(x_i\to y_i,w_i)\in E(G),y_i=u} f_i=\sum\limits_{(x_i\to y_i,w_i)\in E(G),x_i=u} f_i$，即流入该点的流量和等于流出该点的流量和；

定义流 $F$ 的流量 $|F|$ 为 $\sum\limits_{(x_i\to y_i,w_i)\in E(G),y_i=T} f_i$，即流到汇点 $T$ 的流量和。

形象地：

对于一个带权有向图 $G$ 及图上的两个点 $S$（源点）和 $T$（汇点），可以这样看待这张有向图：

• 将点看作水池，边看作水管，则有向边 $(x\to y,w)$ 表示单位时间内最多 $w$ 单位的水可以通过该水管从水池 $x$ 流向水池 $y$；
• 源点 $S$ 是水源，单位时间内能提供无限单位的水；
• 汇点 $T$ 是排水口，单位时间内能接受无限单位的水；

流就是让水从水源流到排水口而不爆水管的方案，流量就是方案中从排水口排走的水量。

#2 网络最大流

定义 2.1（有源汇最大流）

对于一个网络 $(G,S,T)$，定义其上的最大流 $\text{MaxFlow}(G,S,T)$ 为一组满足 $|F|$ 最大的流 $F$。

严格的定义理应是满足 $|F|$ 最大的 $F$ 构成的集合，简便起见就不这样记了。

例如对于这个网络：

其一组最大流（流量为 $9$）如下：（边权为该边使用的流量）

2.1 最大流的求解

2.1.1 反向边的引入

考虑贪心，不断找到从 $S$ 到 $T$ 且容量均 $>0$ 的路径（增广路），即通过这条路径可以让至少 $1$ 的流量从 $S$ 流到 $T$，那么将答案增加 $1$，并将路径上边的容量全部减少 $1$。

定义 2.1.1（增广路）

定义一条增广路为一条从 $S$ 到 $T$ 路径，满足路径上边的容量均 $>0$。

定义 2.1.2 pre（增广）

对于一条增广路 $p$，定义增广操作：

• 令 $w(p)=\min\limits_{(x_i\to y_i,w_i)\in p}\{w_i\}$，即 $p$ 中的边的最小容量；
• 令 $p$ 中边的容量均减少 $w(p)$；
• 令答案（最大流大小）增加 $w(p)$；

那么上述贪心实际上就是不断找增广路进行增广的过程。

但这个贪心是错的，对于一个这样的最大流大小为 $2$ 的网络：

贪心会求出这样的最大流，大小为 $1$：

因此参考反悔贪心，引入反悔（退流）思想。

具体的，对于每条边 $(x\to y,w)$，建立反向边 $(y\to x,0)$：

并修改增广的定义：

定义 2.1.2（增广）

对于一条增广路 $p$，定义增广操作：

• 令 $w(p)=\min\limits_{(x_i\to y_i,w_i)\in p}\{w_i\}$，即 $p$ 中的边的最小容量；
• 令 $p$ 中边的容量均减少 $w(p)$，令 $p$ 中边对应的反向边的容量均增加 $w(p)$；
• 令答案（最大流大小）增加 $w(p)$；

例如对于例子中的网络，进行一轮新的增广后是这样的：

不难发现现在网络中还存在增广路，还能进行增广操作：

那么修正后的贪心就成功求出了一组最大流，最终每条边反向边的容量即为这组最大流中该边使用的流量。

这其实是一个反悔贪心，增广过程中走反向边相当于退流。

容易证明，不断重复上述操作一定能求出一组最大流。

2.1.2 EK 算法

直接模拟上述过程，可以得出求解网络流的朴素算法。

建完图后，用 bfs 来找增广路，并记录下每个点的前驱节点（令其入队的点）以便找到增广路上的边。如果 bfs 时访问到了汇点，那么就找到了一条增广路。

为了储存反向边，不妨令边的编号从 $2$ 开始，并令编号为 $i$ 的边和编号为 $i\oplus 1$ 的边互为反向边。这样实现起来会方便很多。

不断跑 bfs 找增广路去进行增广操作直到 $S$ 和 $T$ 不连通，即可求解出网络的一组最大流。该算法被称作 EK 算法，时间复杂度是 $O((n+m)V)$ 的，其中 $V$ 是最大流的大小，即值域。

2.1.3 dinic 算法

dinic 算法是 EK 算法的一种改进，其可以同时增广多条增广路。

其大体流程如下：

• 每次增广前先跑一次 bfs，将节点按照距离 $S$ 的最短路（边数）$dep_u$ 分层，增广时要求增广路相邻点的 $dep_u$ 恰好相差 $1$；
• 接下来跑 dfs，对所有满足条件的增广路同时进行增广操作；
• 不断重复上两步直至 bfs 时 $S$ 不能到达 $T$，即不存在增广路；

伪代码如下：

int dfs(int u,int w) // u 表示当前节点的编号，w 表示流向当前点的流量，返回值为成功增广的流量
{
    int sum=0;
	遍历所有从 u 出发的边 i
	{
		int v=i 到达的节点;
		if(dep[v]==dep[u]+1)
		{
			int re=dfs(v,min(w,i 的容量));
			if(re!=0)
			{
				更新正向边和反向边的容量;
                w-=re;
				sum+=re;
			}
		}
	}
	return sum;
}
int dinic()
{
    int res=0;
    while(bfs 可以到达 汇点) res+=dfs(s,inf);
    return res;
}

此外，dinic 算法还有几个优化，分别是当前弧优化和断层优化：

• 当前弧优化：把已经“榨干”（容量为 $0$）的边删掉；
• 断层优化：把已经“榨干”的节点“删掉”（return 时若 sum==0 则令 dep[u]=0）；

一般默认会加上这两个优化。

dinic 的最劣复杂度为 $O(n^2m)$，证明考虑每次找到的增广路边数一定最小，故 $dep_T$ 递增；而单次 dfs 中每条增广路都会删掉至少一条边（当前弧优化）故最多有 $m$ 条增广路，而每条增广路长度至多为 $n$。

并且 dinic 在容量均为 $1$ 的网络上的复杂度为 $O(m\sqrt n)$，具体证明及更多关于复杂度的信息可以看Dinic的几种复杂度 - myee - 博客园。

但由于网络流题目的图一般都有特殊性质，故加上优化后的 dinic 常常十分快速，基本不会被卡，在 OI 中最常用。

求解网络流还有 ISAP 和 HLPP，由于太过复杂且 OI 中不考，故不再介绍。

#3 最小费用最大流

在最小费用最大流问题中，每条边新增了一个单位代价 $w_i$，表示这条边流过 $1$ 流量需要 $w_i$ 的代价，需要求解一组总代价最小的最大流。

也可以使用 dinic 算法解决，每次增广单位代价最小的增广路即可，正确性显然。建边时反向边代价为 $-w_i$，而且 bfs 需要换成 spfa，且增广时要求增广路相邻点的 $dep_u$ 恰好相差它们之间的边的代价。

值得注意的是，由于代价可能为 $0$，所以 dfs 时需要防止重复访问点。

#4 有向图最小割

定义 4.1（有向图的割）

对于一个带权有向图 $G$ 及图上的两个点 $S$ 和 $T$，定义一组 $S$ 到 $T$ 的割 $C$ 如下：

• $C\in E(G)$；
• 删掉 $C$ 中的边后 $S$ 不能到达 $T$；

定义割 $C$ 的大小 $|C|$ 为 $\sum\limits_{(x_i\to y_i,w_i)\in C} w_i$，即割中的边权和。

定义 4.2（有向图的最小割）

对于一个带权有向图 $G$ 及图上的两个点 $S$ 和 $T$，定义其最小割 $\text{MinCut}(G,S,T)$ 为 $|C|$ 最小的一组割 $C$。

定理 4.1（最大流等于最小割）

对于一个带权有向图 $G$ 及图上的两个点 $S$ 和 $T$，有：

$|\text{MaxFlow}(G,S,T)|=|\text{MinCut}(G,S,T)|$

证明很简单，首先由于跑完最大流算法后 $S$ 不能到达 $T$，故 $|\text{MaxFlow}(G,S,T)|\ge|\text{MinCut}(G,S,T)|$，又显然 $|\text{MaxFlow}(G,S,T)|\le |\text{MinCut}(G,S,T)|$（最大流中满流的边集构成割），故得证。

更详细的证明可以自行上网寻找。

并且根据一组最大流 $F$，可以简单地构造出最小割：

• 令每条边的剩余容量 $c_i$ 为 $w_i-f_i$；
• 从 $S$ 出发，只经过 $c_i>0$ 的边，求出能到达的点集 $A$；
• 一组最小割 $C$ 即为 $\{(x\to y,w)\in E(G)|x\in A,y\in (V(G)-A)\}$，即一端在 $A$ 中的边的集合；

#5 有上下界网络流

5.1 有上下界循环可行流

$n$ 个点，$m$ 条有向边，每条边有一个流量下界 $l_i$ 和流量上界 $r_i$，求该图的一个循环可行流，即你需要构造 $m$ 个变量 $f_i$ 满足：

• 流量合法：$\forall i,l_i\le f_i\le r_i$；
• 流量平衡：对于每个点 $i$，设 $I_i$ 为 $i$ 的入边集合，$U_i$ 为 $i$ 的出边集合，那么有：$\sum\limits_{j\in I_i} f_j=\sum\limits_{j\in U_i}f_j$；

考虑每条边先钦定流过 $l_i$ 的流量，转化为每条边只有流量上界 $r_i-l_i$，那么流量有可能不平衡。

考虑用点与源点 $S$ 或汇点 $T$ 的连边刻画每个点的额外流量。记 $b_i=\sum\limits_{j\in I_i} l_j-\sum\limits_{j\in U_i}l_j$，即每个点进入的流量减出去的流量，那么：

• 若 $b_i<0$，连接边 $(i\to T,-b_i)$；
• 若 $b_i>0$，连接边 $(S\to i,b_i)$；

原先的边 $i$ 直接连 $(x_i\to y_i,r_i-l_i)$。

跑最大流，若所有 $(i\to T,-b_i)$ 和 $(S\to i,b_i)$ 均满流，则有解，否则无解。设跑完后第 $i$ 条边的流量为 $c_i$，则第 $i$ 条边的流量为 $l_i+c_i$。

时间复杂度和最大流相同。

5.2 有上下界有源汇最大流

考虑将其转化为循环流来消去上下界，设源点为 $s$，汇点为 $t$，则不难发现相当于从 $s$ 出发的流量等于到达 $t$ 的流量，连边 $(t\to s,[0,\infin])$。

跑出循环流后，记 $res$ 为 $(t\to s,[0,\infin])$ 的。接下来把 $(t\to s,[0,\infin])$ 去掉，设第 $i$ 条边在循环流中流过了 $c_i$ 流量，则连接边 $(x_i\to y_i)$ 时：

• 正向边流量为 $r_i-c_i$；
• 反向边流量为 $c_i-l_i$；

则答案即为 $res$ 加上当前图从 $s$ 到 $t$ 的最大流。

5.3 有上下界有源汇最小流

最大流是尽可能从 $s$ 流到 $t$，那么最小流就是尽可能从 $t$ 退回 $s$。

跑出 $t$ 到 $s$ 的最大流 $rf$，答案即为 $res-rf$。

#6 常见模型&技巧

网络流的常见建模