从二分图到网络流
徐晨皓 华南师范大学附属中学
目录
二分图带权最大匹配，KM算法
网络流的概念
用网络流的视角看二分图匹配问题
Dinic算法

二分图最大权匹配
二分图匹配，但是每条边有一个边权，求一个匹配使得边权和最大。

如果不用网络流，可以用KM算法。
考虑到二分图中两个集合中的点并不总是相同，为了能应用 KM 算法解决二分图的最大权匹配，需要先作如下处理：将两个集合中点数比较少的补点，使得两边点数相同，再将不存在的边权重设为 0，这种情况下，问题就转换成求 最大权完美匹配问题，从而能应用 KM 算法求解。
算法流程
首先我们给每个顶点赋一个可行顶标，其中左边标记为lx[i]，右边标记为ly[i]，使得对所有边(u,v)满足w[u][v]<=lx[u]+ly[v]。
那么，考虑这个图G的一个子图G'，使得G'包含G中所有点，但只有那些满足w[u][v]==lx[u]+ly[v]的边。那么，对G'的一个完美匹配，它的权值就等于sum(lx[i]+ly[i],i=1,2,...,n)。也就是说我们需要最大化这个和。
将lx[i]初始赋值为max(w[i][j],j=1,2,...,n)，ly[i]初始赋值为0，然后选一个未匹配点，如同最大匹配一样求增广路。找到增广路就增广，否则，我们可以尝试调整顶标。

算法流程
调整顶标过程中，其实就是要不断的加入新的边，也就是使更多的边满足 lx[i]+ly[j]=w[i][j] 。那么接下来找一条边 (i,j) ，使其满足 i 不在二分图最大匹配中，而 j 在二分图最大匹配中。我们希望这条边加入二分图匹配，就要使这条边满足条件，即顶标和要减少 d=lx[i]+ly[j]−w[i][j] 。
因为此时点 j 在二分图最大匹配中，如果改变顶标会影响其他边，所以可以对于在二分图最大匹配中的任意点 i ,将 lx[i]+=d 或 ly[i]−=d 。为了防止修改完导致部分顶标不满足 lx[x]+ly[y]≥w[x][y] ，每次找的 d 要尽量小。
每次找边复杂度 O(n2)，二分图最大匹配的复杂度 O(n2)，总复杂度 O(n4)。
优化
每次找一遍 d 太慢了，所以我们开个数组slack[j]=min(lx[i]+ly[j]-w[i][j],i=1,2,...,n)，修改在跑增广路的时候修改即可，这样可以省掉找d的时间，使用广度优先搜索跑增广路可以做到复杂度O(n3)。

据说KM算法有时候会比网络流快，不知道真实性。
模板：P6577
板子比较长，大家自行去题解区查阅。
练习
P6577
P4014
网络流
先讲个实际问题：水管流量问题。
从蓄水池A到蓄水池B中间有若干蓄水池和水管，每个水管有个最大流量。现在要从蓄水池A到蓄水池B输水，问一次性最多可以输送多少单位的水。
这就是最大流问题，也是网络流问题的基本来源。

网络流
先讲讲定义。
网络是指一个特殊的有向图 G=(V,E)，其与一般有向图的不同之处在于有容量和源汇点。每条边都有一个被称为容量的权值。
流（flow）是一个从边集 E 到整数集或实数集的函数，其满足以下性质。
容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 0 ≤ f(u,v) ≤ c(u,v)；
流守恒性：除源汇点外，任意结点 u 的净流量为 0。其中，我们定义 u 的净流量为 f(u) =                    。

网络流
定义整个网络的流量为源点 s 的流量 f(s) ，这个值等于汇点 t 的负流量 -f(t)。
如果我们可以通过删掉一些边使得 s 和 t 不连通，那么删掉的这些边可以被称为 G 的一个 s-t 割。记                ，定义这个割的容量为 
网络流的常见问题：最大流和最小割。这两者在数值上相等。


网络流和二分图的关系
事实上绝大部分二分图问题都可以转化为网络流问题。
先拿二分图最大匹配来举例。
记原二分图的左右两部分分别为X和Y，在原二分图的基础上，将所有边转化为X到Y的有向边且设置边权为1，另外添加一个源点，源点到X内的所有点连一条边权为1的有向边，再添加一个汇点，Y内所有点到汇点连一条边权为1的有向边。那么，二分图的最大匹配大小，就等于这个网络流的最大流。
二分图带权最大匹配则可以转化为费用流。
Ford Fulkerson增广
接下来介绍最大流怎么找。
Ford–Fulkerson 增广是计算最大流的一类算法的总称。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。
给定网络 G 及 G 上的流 f，我们做如下定义。
对于边 (u,v)，我们将其容量与流量之差称为剩余容量 cf(u,v)，即 cf(u,v)=c(u,v)-f(u,v)。
我们将 G 中所有结点和剩余容量大于 0 的边构成的子图称为残量网络 Gf，即 Gf=(V,Ef)，其中 Ef={(u,v) | cf(u,v)>0}。
Ford Fulkerson增广
我们将 Gf 上一条从源点 s 到汇点 t 的路径称为增广路。对于一条增广路，我们给每一条边 (u,v) 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。
此外，在 Ford–Fulkerson 增广的过程中，对于每条边 (u,v)，我们都新建一条反向边 (v,u)。我们约定 f(u,v) = -f(v,u)，这一性质可以通过在每次增广时引入退流操作来保证，即 f(u,v) 增加时 f(v,u) 应当减少同等的量。
以上操作是为了保证所找到的最大流的正确性。
Ford Fulkerson增广
如下图，如果我们先找到1->2->3->4这一个流，那么我们无法找到最大流。



但是如果我们引入了退流操作，那么我们就可以再找到1->3->2->4这个流。
正确性
增广路算法的正确性，等价于最大流最小割定理的正确性。
为了证明最大流最小割定理，我们先从一个引理出发：对于网络 G=(V,E)，任取一个流 f 和一个割 {S,T}，总是有 |f|≤||S,T||，其中等号成立当且仅当 {(u,v) | u∈S, v∈T} 的所有边均满流，且 {(u,v) | u∈S, v∈T} 的所有边均空流。
正确性
引理证明：

正确性
接下来我们只需要证明：对任意网络，以上取等条件总能满足。





容易看出，Kőnig 定理是最大流最小割定理的特殊情形。实际上，它们都和线性规划中的对偶有关。

增广路算法的各种实现
设图中有n个顶点和m条边。
朴素实现：每次增广1的流量，复杂度O(m*max(|f|))。
Edmonds–Karp 算法：利用BFS，复杂度上界O(nm2)。
Dinic算法：BFS分层+DFS增广，复杂度上界O(n2m)。特殊图可能更优。
MPM算法：考虑顶点的容量来BFS，复杂度O(n3)。
ISAP算法：Dinic+增广时重分层，复杂度同Dinic，常数优化。
预流推进算法/HLPP算法：O(n2 sqrt(m))，但是数据范围卡的很紧。
OI里最常用的是Dinic算法。

Dinic算法
在增广前先对 Gf 做 BFS 分层，即根据结点 u 到源点 s 的距离 d(u) 把结点分成若干层。令经过 u 的流量只能流向下一层的结点 v，即删除 u 向层数标号相等或更小的结点的出边，我们称 Gf 剩下的部分为层次图。形式化地，我们称 GL = (V,EL) 是 Gf = (V,Ef) 的层次图，其中 EL = {(u,v) | (u,v) ∈ Ef, d(u) + 1 = d(v) }。
如果我们在层次图 GL 上找到一个最大的增广流 fb，使得仅在 GL 上是不可能找出更大的增广流的，则我们称 fb 是 GL 的阻塞流。
注：定义阻塞流所用的增广流，指的是当前所有增广流的并。

Dinic算法
定义层次图和阻塞流后，Dinic 算法的流程如下。
1、在 Gf 上 BFS 出层次图 GL。
2、在 GL 上 DFS 出阻塞流 fb。
3、将 fb 并到原先的流 f 中，即 f ← f + fb。
4、重复以上过程直到不存在从 s 到 t 的路径。
此时的 f 即为最大流。
当前弧优化
注意到在 GL 上 DFS 的过程中，如果结点 u 同时具有大量入边和出边，并且 u 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 u 这个局部的时间复杂度最坏可达 O(m2)。为避免这一缺陷，如果某一时刻我们已经知道边 (u,v) 已经增广到极限（边 (u,v) 已无剩余容量或 v 的后侧已增广至阻塞），则 u 的流量没有必要再尝试流向出边 (u,v)。据此，对于每个结点 u，我们维护 u 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。
时间复杂度分析
在应用当前弧优化的前提下，先证明单轮增广中 DFS 求阻塞流的时间复杂度是 O(nm)。
考虑阻塞流 fb 中的每条增广路，它们都是在 GL 上每次沿当前弧跳转而得到的结果，其中每条增广路经历的跳转次数不可能多于 n。
每找到一条增广路就有一条饱和边消失（剩余容量清零）。考虑阻塞流 fb 中的每条增广路，我们将被它们清零的饱和边形成的边集记作 E1。考虑到 GL 分层的性质，饱和边消失后其反向边不可能在同一轮增广内被其他增广路经过，因此，E1 是 EL 的子集。
此外，对于沿当前弧跳转但由于某个位置阻塞所以没有成功得到增广路的情形，我们将这些不完整的路径上的最后一条边形成的边集记作 E2。E2 的成员不饱和，所以 E1 与 E2 不交，且 E1 ∪ E2 仍是 EL 的子集。
由于 E1 ∪ E2 的每个成员都没有花费超过 n 次跳转（且在使用多路增广优化后一些跳转将被重复计数），因此，综上所述，DFS 过程中的总跳转次数不可能多于 nm。
时间复杂度分析
接下来证明层次图的层数在增广过程中严格单增，这样的话增广轮数是O(n)的。
证明较长，分两页截图。
时间复杂度分析
接上：
时间复杂度分析
如果需要令 Dinic 算法的实际运行时间接近其理论上界，我们需要构造有特殊性质的网络作为输入。由于在算法竞赛实践中，对于网络流知识相关的考察常侧重于将原问题建模为网络流问题的技巧。此时，我们的建模通常不包含令 Dinic 算法执行缓慢的特殊性质；恰恰相反，Dinic 算法在大部分图上效率非常优秀。
如果所有边的容量都是1，那么每次增广的时间复杂度是O(m)，增广轮数是O(m1/2)或者O(n2/3)。
对于二分图最大匹配问题，Dinic算法的复杂度为O(mn1/2)。

板子：P3376
请大家利用Dinic算法完成这个题，以及二分图最大匹配的模板题。
例题：P2740
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
输入：第一行排水沟数量n和交叉点数量m，交叉点1是水潭，交叉点m是小溪。接下来n行每行三个整数为排水沟起点si，终点ei，流量ci。
输出：一个整数表示最大流量。
解析
最大流板子。
练习
P3376
P2740
P2763
P3254
P4662
P6094
最小割
最小割的求法和最大流求法一样。
如果需要输出最小割方案，我们可以通过从源点 s 开始 DFS，每次走残量大于 0 的边，找到所有 S 点集内的点。
如果需要最小化割边数量，那么先求出最小割，把没有满流的边容量改成 正无穷，满流的边容量改成 1，重新跑一遍最小割就可求出最小割边数量。

最小割问题模型
1、有 n 个物品和两个集合 A,B，如果一个物品没有放入 A 集合会花费 ai，没有放入 B 集合会花费 bi；还有若干个形如 ui,vi,wi 限制条件，表示如果 ui 和 vi 同时不在一个集合会花费 wi。每个物品必须且只能属于一个集合，求最小的代价。
解析
这是一个经典的 二者选其一 的最小割题目。我们对于每个集合设置源点 s 和汇点 t，第 i 个点由 s 连一条容量为 ai 的边、向 t 连一条容量为 bi 的边。对于限制条件 u,v,w，我们在 u,v 之间连容量为 w 的双向边。
注意到当源点和汇点不相连时，代表这些点都选择了其中一个集合。如果将连向 s 或 t 的边割开，表示不放在 A 或 B 集合，如果把物品之间的边割开，表示这两个物品不放在同一个集合。
最小割就是最小花费。
例：洛谷P1361
最小割问题模型
最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。

最小割问题模型
最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。
做法：建立超级源点 s 和超级汇点 t，若节点 u 权值为正，则 s 向 u 连一条有向边，边权即为该点点权；若节点 u 权值为负，则由 u 向 t 连一条有向边，边权即为该点点权的相反数。原图上所有边权改为正无穷。跑网络最大流，将所有正权值之和减去最大流，即为答案。
例题：P1344
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。
送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
输入输出
输入：第一行仓库数量n和卡车数量m，1号仓库是发货仓，n号仓库是收货仓，接下来m行每行三个整数分别是卡车起点si，终点ei，损失ci。
输出：两个空格分开的整数，第一个表示最小损失，第二个表示最少停车数。

解析
最小割裸题，不过还要求最小边数。
按照上面的全部边权转1的做法再跑一遍即可。
练习
P2598
P1935
P2762

费用流
给定一个网络 G=(V,E)，每条边除了有容量限制 c(u,v)，还有一个单位流量的费用 w(u,v)。当 (u,v) 的流量为 f(u,v) 时，需要花费 f(u,v)×w(u,v) 的费用。w也满足斜对称性，即 w(u,v)=-w(v,u)。
则该网络中总花费最小的最大流称为最小费用最大流。也就是流量最大的前提下最小化费用。
主体是SSP算法，利用Primal-Dual算法处理负环。
SSP算法
一个贪心算法。它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。如果图上存在单位费用为负的圈，SSP 算法无法正确求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈。
实现上很简单，只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。
但是时间复杂度是O(nm*max|f|)，是伪多项式的。
Primal-Dual算法
如果用Bellman-Ford(SPFA)跑最短路，时间复杂度O(nm)太大了，但是Dijkstra没法处理负边。因此考虑调整边权。
Primal-Dual 原始对偶算法的思路与 Johnson 全源最短路径算法类似，通过为每个点设置一个势能，将网络上所有边的费用（下面简称为边权）全部变为非负值，从而可以应用 Dijkstra 算法找出网络上单位费用最小的增广路。
首先跑一次最短路，求出源点到每个点的最短距离（也是该点的初始势能）hi。接下来和 Johnson 算法一样，对于一条从 u 到 v，单位费用为 w 的边，将其边权重置为 w+hu-hv。
Primal-Dual算法
与常规的最短路问题不同的是，每次增广后图的形态会发生变化，这种情况下各点的势能需要更新。
如何更新呢？先给出结论，设增广后从源点到 i 号点的最短距离为 d'i（这里的距离为重置每条边边权后得到的距离），只需给 hi 加上 d'i 即可。下面我们证明，这样更新边权后，图上所有边的边权均为非负。
Primal-Dual算法
容易发现，在一轮增广后，由于一些 (i,j) 边在增广路上，残量网络上会相应多出一些 (j,i) 边，且一定会满足 d'i+(w(i,j)+hi-hj)=d'j（否则 (i,j) 边就不会在增广路上了）。稍作变形后可以得到 w(j,i)+(hj+d'j)-(hi+d'i)=0。因此新增的边的边权非负。
而对于原有的边，在增广前，d'i+(w(i,j)+hi-hj) - d'j ≥ 0，因此 w(i,j)+(d'i+hi)-(d'j+hj) ≥ 0，即用 hi+d'i 作为新势能并不会使 (i,j) 的边权变为负。
综上，增广后所有边的边权均非负，使用 Dijkstra 算法可以正确求出图上的最短路。
板子：P3381
最小费用最大流板子。
例题：P2045
方格取数加强版，从走2次变成走K次。

例题：P2045
方格取数加强版，从走2次变成走K次。
建图：
超级源点和超级汇点分别连向(1,1)和(n,n)，容量为k，费用为0，仅表示一共可以走k次；
对于方格中的每个点，拆成两个点，分别为入点和出点。入点和出点之间连两条边，一条容量为1，费用为点的权值，表示每个点的数只可以取一次；另一条容量为inf，费用为0，仅表示可以经过无数次；
对于在其下方或右边点的点，连一条容量为inf，费用为0的边，表示且仅表示一种连通的关系。然后费用流即可。
练习
P3381
P2045
P2457
P3159
上下界网络流
从二分图到网络流
徐晨皓 华南师范大学附属中学
目录
二分图带权最大匹配，KM算法
网络流的概念
用网络流的视角看二分图匹配问题
Dinic算法

二分图最大权匹配
二分图匹配，但是每条边有一个边权，求一个匹配使得边权和最大。

如果不用网络流，可以用KM算法。
考虑到二分图中两个集合中的点并不总是相同，为了能应用 KM 算法解决二分图的最大权匹配，需要先作如下处理：将两个集合中点数比较少的补点，使得两边点数相同，再将不存在的边权重设为 0，这种情况下，问题就转换成求 最大权完美匹配问题，从而能应用 KM 算法求解。
算法流程
首先我们给每个顶点赋一个可行顶标，其中左边标记为lx[i]，右边标记为ly[i]，使得对所有边(u,v)满足w[u][v]<=lx[u]+ly[v]。
那么，考虑这个图G的一个子图G'，使得G'包含G中所有点，但只有那些满足w[u][v]==lx[u]+ly[v]的边。那么，对G'的一个完美匹配，它的权值就等于sum(lx[i]+ly[i],i=1,2,...,n)。也就是说我们需要最大化这个和。
将lx[i]初始赋值为max(w[i][j],j=1,2,...,n)，ly[i]初始赋值为0，然后选一个未匹配点，如同最大匹配一样求增广路。找到增广路就增广，否则，我们可以尝试调整顶标。

算法流程
调整顶标过程中，其实就是要不断的加入新的边，也就是使更多的边满足 lx[i]+ly[j]=w[i][j] 。那么接下来找一条边 (i,j) ，使其满足 i 不在二分图最大匹配中，而 j 在二分图最大匹配中。我们希望这条边加入二分图匹配，就要使这条边满足条件，即顶标和要减少 d=lx[i]+ly[j]−w[i][j] 。
因为此时点 j 在二分图最大匹配中，如果改变顶标会影响其他边，所以可以对于在二分图最大匹配中的任意点 i ,将 lx[i]+=d 或 ly[i]−=d 。为了防止修改完导致部分顶标不满足 lx[x]+ly[y]≥w[x][y] ，每次找的 d 要尽量小。
每次找边复杂度 O(n2)，二分图最大匹配的复杂度 O(n2)，总复杂度 O(n4)。
优化
每次找一遍 d 太慢了，所以我们开个数组slack[j]=min(lx[i]+ly[j]-w[i][j],i=1,2,...,n)，修改在跑增广路的时候修改即可，这样可以省掉找d的时间，使用广度优先搜索跑增广路可以做到复杂度O(n3)。

据说KM算法有时候会比网络流快，不知道真实性。
模板：P6577
板子比较长，大家自行去题解区查阅。
练习
P6577
P4014
网络流
先讲个实际问题：水管流量问题。
从蓄水池A到蓄水池B中间有若干蓄水池和水管，每个水管有个最大流量。现在要从蓄水池A到蓄水池B输水，问一次性最多可以输送多少单位的水。
这就是最大流问题，也是网络流问题的基本来源。

网络流
先讲讲定义。
网络是指一个特殊的有向图 G=(V,E)，其与一般有向图的不同之处在于有容量和源汇点。每条边都有一个被称为容量的权值。
流（flow）是一个从边集 E 到整数集或实数集的函数，其满足以下性质。
容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 0 ≤ f(u,v) ≤ c(u,v)；
流守恒性：除源汇点外，任意结点 u 的净流量为 0。其中，我们定义 u 的净流量为 f(u) =                    。

网络流
定义整个网络的流量为源点 s 的流量 f(s) ，这个值等于汇点 t 的负流量 -f(t)。
如果我们可以通过删掉一些边使得 s 和 t 不连通，那么删掉的这些边可以被称为 G 的一个 s-t 割。记                ，定义这个割的容量为 
网络流的常见问题：最大流和最小割。这两者在数值上相等。


网络流和二分图的关系
事实上绝大部分二分图问题都可以转化为网络流问题。
先拿二分图最大匹配来举例。
记原二分图的左右两部分分别为X和Y，在原二分图的基础上，将所有边转化为X到Y的有向边且设置边权为1，另外添加一个源点，源点到X内的所有点连一条边权为1的有向边，再添加一个汇点，Y内所有点到汇点连一条边权为1的有向边。那么，二分图的最大匹配大小，就等于这个网络流的最大流。
二分图带权最大匹配则可以转化为费用流。
Ford Fulkerson增广
接下来介绍最大流怎么找。
Ford–Fulkerson 增广是计算最大流的一类算法的总称。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。
给定网络 G 及 G 上的流 f，我们做如下定义。
对于边 (u,v)，我们将其容量与流量之差称为剩余容量 cf(u,v)，即 cf(u,v)=c(u,v)-f(u,v)。
我们将 G 中所有结点和剩余容量大于 0 的边构成的子图称为残量网络 Gf，即 Gf=(V,Ef)，其中 Ef={(u,v) | cf(u,v)>0}。
Ford Fulkerson增广
我们将 Gf 上一条从源点 s 到汇点 t 的路径称为增广路。对于一条增广路，我们给每一条边 (u,v) 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。
此外，在 Ford–Fulkerson 增广的过程中，对于每条边 (u,v)，我们都新建一条反向边 (v,u)。我们约定 f(u,v) = -f(v,u)，这一性质可以通过在每次增广时引入退流操作来保证，即 f(u,v) 增加时 f(v,u) 应当减少同等的量。
以上操作是为了保证所找到的最大流的正确性。
Ford Fulkerson增广
如下图，如果我们先找到1->2->3->4这一个流，那么我们无法找到最大流。



但是如果我们引入了退流操作，那么我们就可以再找到1->3->2->4这个流。
正确性
增广路算法的正确性，等价于最大流最小割定理的正确性。
为了证明最大流最小割定理，我们先从一个引理出发：对于网络 G=(V,E)，任取一个流 f 和一个割 {S,T}，总是有 |f|≤||S,T||，其中等号成立当且仅当 {(u,v) | u∈S, v∈T} 的所有边均满流，且 {(u,v) | u∈S, v∈T} 的所有边均空流。
正确性
引理证明：

正确性
接下来我们只需要证明：对任意网络，以上取等条件总能满足。





容易看出，Kőnig 定理是最大流最小割定理的特殊情形。实际上，它们都和线性规划中的对偶有关。

增广路算法的各种实现
设图中有n个顶点和m条边。
朴素实现：每次增广1的流量，复杂度O(m*max(|f|))。
Edmonds–Karp 算法：利用BFS，复杂度上界O(nm2)。
Dinic算法：BFS分层+DFS增广，复杂度上界O(n2m)。特殊图可能更优。
MPM算法：考虑顶点的容量来BFS，复杂度O(n3)。
ISAP算法：Dinic+增广时重分层，复杂度同Dinic，常数优化。
预流推进算法/HLPP算法：O(n2 sqrt(m))，但是数据范围卡的很紧。
OI里最常用的是Dinic算法。

Dinic算法
在增广前先对 Gf 做 BFS 分层，即根据结点 u 到源点 s 的距离 d(u) 把结点分成若干层。令经过 u 的流量只能流向下一层的结点 v，即删除 u 向层数标号相等或更小的结点的出边，我们称 Gf 剩下的部分为层次图。形式化地，我们称 GL = (V,EL) 是 Gf = (V,Ef) 的层次图，其中 EL = {(u,v) | (u,v) ∈ Ef, d(u) + 1 = d(v) }。
如果我们在层次图 GL 上找到一个最大的增广流 fb，使得仅在 GL 上是不可能找出更大的增广流的，则我们称 fb 是 GL 的阻塞流。
注：定义阻塞流所用的增广流，指的是当前所有增广流的并。

Dinic算法
定义层次图和阻塞流后，Dinic 算法的流程如下。
1、在 Gf 上 BFS 出层次图 GL。
2、在 GL 上 DFS 出阻塞流 fb。
3、将 fb 并到原先的流 f 中，即 f ← f + fb。
4、重复以上过程直到不存在从 s 到 t 的路径。
此时的 f 即为最大流。
当前弧优化
注意到在 GL 上 DFS 的过程中，如果结点 u 同时具有大量入边和出边，并且 u 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 u 这个局部的时间复杂度最坏可达 O(m2)。为避免这一缺陷，如果某一时刻我们已经知道边 (u,v) 已经增广到极限（边 (u,v) 已无剩余容量或 v 的后侧已增广至阻塞），则 u 的流量没有必要再尝试流向出边 (u,v)。据此，对于每个结点 u，我们维护 u 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。
时间复杂度分析
在应用当前弧优化的前提下，先证明单轮增广中 DFS 求阻塞流的时间复杂度是 O(nm)。
考虑阻塞流 fb 中的每条增广路，它们都是在 GL 上每次沿当前弧跳转而得到的结果，其中每条增广路经历的跳转次数不可能多于 n。
每找到一条增广路就有一条饱和边消失（剩余容量清零）。考虑阻塞流 fb 中的每条增广路，我们将被它们清零的饱和边形成的边集记作 E1。考虑到 GL 分层的性质，饱和边消失后其反向边不可能在同一轮增广内被其他增广路经过，因此，E1 是 EL 的子集。
此外，对于沿当前弧跳转但由于某个位置阻塞所以没有成功得到增广路的情形，我们将这些不完整的路径上的最后一条边形成的边集记作 E2。E2 的成员不饱和，所以 E1 与 E2 不交，且 E1 ∪ E2 仍是 EL 的子集。
由于 E1 ∪ E2 的每个成员都没有花费超过 n 次跳转（且在使用多路增广优化后一些跳转将被重复计数），因此，综上所述，DFS 过程中的总跳转次数不可能多于 nm。
时间复杂度分析
接下来证明层次图的层数在增广过程中严格单增，这样的话增广轮数是O(n)的。
证明较长，分两页截图。
时间复杂度分析
接上：
时间复杂度分析
如果需要令 Dinic 算法的实际运行时间接近其理论上界，我们需要构造有特殊性质的网络作为输入。由于在算法竞赛实践中，对于网络流知识相关的考察常侧重于将原问题建模为网络流问题的技巧。此时，我们的建模通常不包含令 Dinic 算法执行缓慢的特殊性质；恰恰相反，Dinic 算法在大部分图上效率非常优秀。
如果所有边的容量都是1，那么每次增广的时间复杂度是O(m)，增广轮数是O(m1/2)或者O(n2/3)。
对于二分图最大匹配问题，Dinic算法的复杂度为O(mn1/2)。

板子：P3376
请大家利用Dinic算法完成这个题，以及二分图最大匹配的模板题。
例题：P2740
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
输入：第一行排水沟数量n和交叉点数量m，交叉点1是水潭，交叉点m是小溪。接下来n行每行三个整数为排水沟起点si，终点ei，流量ci。
输出：一个整数表示最大流量。
解析
最大流板子。
练习
P3376
P2740
P2763
P3254
P4662
P6094
最小割
最小割的求法和最大流求法一样。
如果需要输出最小割方案，我们可以通过从源点 s 开始 DFS，每次走残量大于 0 的边，找到所有 S 点集内的点。
如果需要最小化割边数量，那么先求出最小割，把没有满流的边容量改成 正无穷，满流的边容量改成 1，重新跑一遍最小割就可求出最小割边数量。

最小割问题模型
1、有 n 个物品和两个集合 A,B，如果一个物品没有放入 A 集合会花费 ai，没有放入 B 集合会花费 bi；还有若干个形如 ui,vi,wi 限制条件，表示如果 ui 和 vi 同时不在一个集合会花费 wi。每个物品必须且只能属于一个集合，求最小的代价。
解析
这是一个经典的 二者选其一 的最小割题目。我们对于每个集合设置源点 s 和汇点 t，第 i 个点由 s 连一条容量为 ai 的边、向 t 连一条容量为 bi 的边。对于限制条件 u,v,w，我们在 u,v 之间连容量为 w 的双向边。
注意到当源点和汇点不相连时，代表这些点都选择了其中一个集合。如果将连向 s 或 t 的边割开，表示不放在 A 或 B 集合，如果把物品之间的边割开，表示这两个物品不放在同一个集合。
最小割就是最小花费。
例：洛谷P1361
最小割问题模型
最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。

最小割问题模型
最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。
做法：建立超级源点 s 和超级汇点 t，若节点 u 权值为正，则 s 向 u 连一条有向边，边权即为该点点权；若节点 u 权值为负，则由 u 向 t 连一条有向边，边权即为该点点权的相反数。原图上所有边权改为正无穷。跑网络最大流，将所有正权值之和减去最大流，即为答案。
例题：P1344
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。
送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
输入输出
输入：第一行仓库数量n和卡车数量m，1号仓库是发货仓，n号仓库是收货仓，接下来m行每行三个整数分别是卡车起点si，终点ei，损失ci。
输出：两个空格分开的整数，第一个表示最小损失，第二个表示最少停车数。

解析
最小割裸题，不过还要求最小边数。
按照上面的全部边权转1的做法再跑一遍即可。
练习
P2598
P1935
P2762

费用流
给定一个网络 G=(V,E)，每条边除了有容量限制 c(u,v)，还有一个单位流量的费用 w(u,v)。当 (u,v) 的流量为 f(u,v) 时，需要花费 f(u,v)×w(u,v) 的费用。w也满足斜对称性，即 w(u,v)=-w(v,u)。
则该网络中总花费最小的最大流称为最小费用最大流。也就是流量最大的前提下最小化费用。
主体是SSP算法，利用Primal-Dual算法处理负环。
SSP算法
一个贪心算法。它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。如果图上存在单位费用为负的圈，SSP 算法无法正确求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈。
实现上很简单，只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。
但是时间复杂度是O(nm*max|f|)，是伪多项式的。
Primal-Dual算法
如果用Bellman-Ford(SPFA)跑最短路，时间复杂度O(nm)太大了，但是Dijkstra没法处理负边。因此考虑调整边权。
Primal-Dual 原始对偶算法的思路与 Johnson 全源最短路径算法类似，通过为每个点设置一个势能，将网络上所有边的费用（下面简称为边权）全部变为非负值，从而可以应用 Dijkstra 算法找出网络上单位费用最小的增广路。
首先跑一次最短路，求出源点到每个点的最短距离（也是该点的初始势能）hi。接下来和 Johnson 算法一样，对于一条从 u 到 v，单位费用为 w 的边，将其边权重置为 w+hu-hv。
Primal-Dual算法
与常规的最短路问题不同的是，每次增广后图的形态会发生变化，这种情况下各点的势能需要更新。
如何更新呢？先给出结论，设增广后从源点到 i 号点的最短距离为 d'i（这里的距离为重置每条边边权后得到的距离），只需给 hi 加上 d'i 即可。下面我们证明，这样更新边权后，图上所有边的边权均为非负。
Primal-Dual算法
容易发现，在一轮增广后，由于一些 (i,j) 边在增广路上，残量网络上会相应多出一些 (j,i) 边，且一定会满足 d'i+(w(i,j)+hi-hj)=d'j（否则 (i,j) 边就不会在增广路上了）。稍作变形后可以得到 w(j,i)+(hj+d'j)-(hi+d'i)=0。因此新增的边的边权非负。
而对于原有的边，在增广前，d'i+(w(i,j)+hi-hj) - d'j ≥ 0，因此 w(i,j)+(d'i+hi)-(d'j+hj) ≥ 0，即用 hi+d'i 作为新势能并不会使 (i,j) 的边权变为负。
综上，增广后所有边的边权均非负，使用 Dijkstra 算法可以正确求出图上的最短路。
板子：P3381
最小费用最大流板子。
例题：P2045
方格取数加强版，从走2次变成走K次。

例题：P2045
方格取数加强版，从走2次变成走K次。
建图：
超级源点和超级汇点分别连向(1,1)和(n,n)，容量为k，费用为0，仅表示一共可以走k次；
对于方格中的每个点，拆成两个点，分别为入点和出点。入点和出点之间连两条边，一条容量为1，费用为点的权值，表示每个点的数只可以取一次；另一条容量为inf，费用为0，仅表示可以经过无数次；
对于在其下方或右边点的点，连一条容量为inf，费用为0的边，表示且仅表示一种连通的关系。然后费用流即可。
练习
P3381
P2045
P2457
P3159
上下界网络流