有源汇最大流算法家族

EK

BFS 寻找最短增广路。

时间复杂度 $O(n^2m^2)$ 。

Dinic

Dinic 是 EK 的优化。

BFS 得到距离标号，用 DFS 同时增广相同长度的增广路。

反向标号：从 $T$ 开始 BFS 重算距离标号，从 $S$ 开始 DFS。

时间复杂度 $O(n^2m)$ 。

在边权全为 $1$ 的图上跑最大流的时间复杂度为 $O(\min\{n^{\frac23}m,m^{\frac32}\})$ 。

ISAP

ISAP 可视为 Dinic 的优化。

在 DFS 之后直接 $\text{dist}_u=\min\{\text{dist}_v\}+1$ 。

再加一个 $\text{gap}_x$ 表示 $\sum[\text{dist}_u=x]$ 。若 $\text{gap}_x$ 断层，则不可能再找到增广路，算法结束。

时间复杂度 $O(n^2m)$ 。

LCT + Dinic

狗都不写。

PP

所谓预流推进，就是不管点 $u$ 能流多少，都给它最多的流量。如果流不完，就再还回来。

但要是图上有环，就会出现你把流量推给我、我把流量推给你的情况。为了避免，我们像 SAP 那样对每个点 $u$ 记录一个 $\text{dist}_u$ ，表示每个点的高度。只有高的点才能往低的点流。

初始时，规定源点的高度为 $n$ ，汇点的高度为 $0$ ，其它点的高度为到汇点的距离。每碰到一个因高度过低导致有流不出去的残余流量的点，就将它的高度设为 $\min_{(u,v)\in E}\{\text{dist}_v+1\}$ 。

用队列维护所有有参与容量的节点（称为活动节点），每次扩展队首节点。注意实现时源点可以往与之相连的任何点扩展，而其它点 $u$ 只能向 $\text{dist}_v=\text{dist}_u-1$ 的点 $v$ 扩展。

效率据说比较低下。

HLPP

全称最高标号预流推进算法。字面意思，每次扩展 $\text{dist}$ 最大的活动节点。

直接把 PP 的队列换成优先队列常数稍有些大，但这是常用写法。也可以每种 $\text{dist}$ 都开一个队列，可以优化常数。

可以证明该算法的时间复杂度为 $O(n^2\sqrt m)$ 。

Gap + HLPP

跟 ISAP 差不多，发现图上出现 $\text{dist}=x$ 了断层，则将 $\text{dist}_u>x$ 的 $\text{dist}_u$ 设为 $n+1$ ，使 $u$ 的流量直接流回源点。

上下界网络流家族

无源汇上下界可行流

记 $(u,v,x,y)$ 表示一条从 $u$ 到 $v$ 的、下界为 $x$ 、上界为 $y$ 的边。

先给原图上的边假定都流过了下界 $x$ （实际上可以钦定为 $[x,y]$ 中任意值），并统计每个点 $u$ 在此流量下的入流量 $\text{in}_u$ 和出流量 $\text{out}_u$ 。

现在流量并不平衡。尝试找环，给一些边新增一些流量达到流量平衡。

在新图上新建源点 $S$ 和汇点 $T$ 。对于原图上的边 $(u,v,x,y)$ ，连边 $(u,v,y-x)$ 。对于每个点 $u$ ，构造：

若 $\text{in}_u>\text{out}_u$ ，则连边 $(S,u,\text{in}_u-\text{out}_u)$ 。
否则，连边 $(u,T,\text{out}_u-\text{in}_u)$ 。
注意：入流量大，连源点；出流量大，连汇点！

跑一遍有源汇最大流，若从 $S$ 出发的边（或到达 $T$ 的边）都满流，则找到可行流。原图上的边的流量，等于新图上该边的流量，加上开始时给这条边钦定的流量，即下界 $x$ 。

若允许负流量，则分类讨论 $x,y$ 与 $0$ 的关系，建正向 / 反向边（或者都建）。

有源汇上下界可行流

对于原源点和汇点 $s,t$ ，建边 $(t,s,+\infty)$ 。转化为『无源汇上下界可行流』求解。

若允许负流量，则还需建边 $(s,t,+\infty)$ 。

无源汇上下界最大 / 小流

指钦定边最大流 / 点最大流。详见『最大流等价性』。

有源汇上下界最大流

先套用『有源汇上下界可行流』，判断是否有解。

若有解，删掉附加源汇点 $S,T$ 和边 $(t,s,+\infty)$ ，在残量网络上跑 $s-t$ 的有源汇最大流。答案为『有源汇上下界可行流』中 $t-s$ 的流量与残量网络上 $s-t$ 的最大流之和。

也可以不删除边 $(t,s,+\infty)$ ，那么 $s-t$ 的最大流恰等于答案。

若允许负流量，记得再减掉『有源汇上下界可行流』中 $s-t$ 的流量。

有源汇上下界最小流

将『有源汇上下界最大流』中「跑 $s-t$ 的有源汇最大流」改成「跑反图 $t-s$ 的有源汇最大流」即可。答案为『有源汇上下界可行流』中 $t-s$ 的流量与残量网络上 $t-s$ 的最大流之差。（应该是这样吧）

可行流等价性

以下可行流一一对应：

有源汇可行流。
连边 $(T,S,-\infty,+\infty)$ 得到的无源汇可行流。
直接将 $S$ 和 $T$ 看做一个点得到的无源汇可行流。

最大流等价性

以下最大流一一对应：

有源汇最大流。
连边 $(T,S,-\infty,+\infty)$ 得到的无源汇边最大流。
直接将 $S$ 和 $T$ 看做一个点得到的无源汇点最大流。（需保证 $S$ 无入边， $T$ 无出边）

增广路定理扩展

最大流等价于无源 - 汇增广路。

最小流等价于无汇 - 源增广路。

费用流算法家族

每次只能找费用最短路。

错误算法：Dinic + SPFA

费用为零的增广环会出现指数复杂度乃至死循环。

正确算法：原始对偶算法

类似于 Jhonson，给每个点赋一个势，定义为上次增广的 $\text{dist}$ 。可以将 SPFA 换为 Dijkstra。

实际问题中，SPFA 往往不会出错且随机图上表现良好；而 Dijkstra 因为多带个 $\log$ 反而容易超时。

注意稠密图上最好使用朴素 Dijkstra 避免复杂度劣化。

有负环费用流处理

增广路算法由于实现中存在最短路算法，无法处理存在费用负圈的最小费用流问题。

消圈算法本身就有消除负圈的过程，但由于效率低下，在 OI 中并不实用。

我们考虑利用上下界网络流的技术来解决负圈的问题。

—— hezlik

将所有负边 $(u,v,f,c)$ 强制满流，并建边 $(v,u,f,-c)$ 用于退流。

我们还是新建源点 $S$ 和汇点 $T$ 。对于每个点 $u$ ，统计强制满流的边带来的出、入流量，并构造：

若 $\text{in}_u>\text{out}_u$ ，则连边 $(S,u,\text{in}_u-\text{out}_u)$ 。
否则，连边 $(u,T,\text{out}_u-\text{in}_u)$ 。
注意：入流量大，连源点；出流量大，连汇点！

求得 $S-T$ 的最小费用最大流后，得到可行流。再删掉 $S,T$ 求得 $s-t$ 的最小费用最大流。后者最大流即为原图最大流，原图最小费用为三者之和。

可行费用流

流到亏钱为止。

整数流量原理

如果每条边的容量都是整数，那么：

最大流为整数。
存在至少一个最大流的流量网络，每条边的流量都是整数。

$k$ 的倍数。

POJ1637. 混合图欧拉回路

题意：给出 $n$ 个点 $m$ 条边的混合图，有些边有方向，有些边没有方向。求在每条边经过恰好一次的前提下是否存在欧拉回路。

$n\le200$ ， $m\le10^3$ 。

给无向边定向，使得每个点入度等于出度。将 $\{-1,1\}$ 的值域转化成 $\{0,1\}$ 即可。

最小割

最大流 = 最小割。

最小割方案

利用 Dinic 最后一次 BFS。或 ISAP 最后一次断层。不用再搜一遍

最大权闭合子图

$w=$ 正 $-$ 割。

二分图

一些定理

二分图：最大匹配 = 最小点覆盖。
一般图：最大独立集 = 总点数 - 最小点覆盖。
DAG 上最小不相交路径覆盖 = 总点数 - 拆点后二分图最大匹配数。
注意 Dinic 跑二分图最大匹配是 $O(m\sqrt n)$ 的。

一些方案输出

最小点覆盖：先求出一组最大匹配。从所有未匹配的左部点开始，只走向右的非匹配边和向左的匹配边，将到达的点染黑。方案为左部点中白点 + 右部点中黑点。
最大独立集：取最小点覆盖的补集即可。

狄尔沃斯定理 Dilworth

偏序集：可以理解为传递闭包后的 DAG，即对于一个 DAG，若 $u$ 可到达 $v$ ，则在新图上连边 $(u,v)$ 。

反链：互相不可到达的点集。

狄尔沃斯定理：DAG 上最长反链，等于最小可相交路径覆盖。

这个等价于，偏序集中最长反链，等于最小不相交链覆盖。

狄尔沃斯定理对偶定理：DAG 上最长链，等于最小反链覆盖。

这个等价于，偏序集中最长链，等于最大独立集。