flow

注：这是我很早写的文章（大概一年前），所以存在大量胡话，不保证正确性。

$\bf\sf 0x01$ 网络最大流

算法

Dinic

算法过程：

• 建出原图 $G$ 的层次图
• dfs 找出阻塞流 $f$，并加入原最大流中
  • 当前弧优化，对于已经增广到极限的边 $(u,v)$，可以直接修改 $h$ 数组不遍历，注意每次递归完都要重新赋值一遍。
  • 若当前前面流到 $u$ 的流已经流完，直接返回。

时间复杂度：

• 对于普通图，时间复杂度为 $\mathcal O(n^2m)$。
• 对于单位容量网络，时间复杂度为 $\mathcal O(m\min(\sqrt{m},\sqrt[3]{n^2}))$。
• 特殊的，对于二分图最大匹配问题，时间复杂度为 $\mathcal O(m\sqrt n)$。

ISAP

算法过程：

• 倒序 bfs，并从 $0$ 开始给 $lev$ 赋值
• 重复以下过程，直至 $lev_s\ge n$
  • dfs 找出阻塞流 $f$，并加入原最大流中
    • 当前弧优化 + 无流返回
  • 未返回，说明 $u$ 的所有出边已经遍历完毕而且 $u$ 还有残余流量，有以下两种更新方法：
    • 此时只要将 $lev_u\gets lev_u + 1$，即每次一定会对仍然还有流的节点 $lev$ 增加，而且因为有流就有连续路径，所以不存在断流。因为最多增广 $n$ 次，于是保证了时间复杂度，这种更新比下面好写很多。
    • 此时可以更新 $lev$ 数组为 $\min\{lev_v\}+1$，相当于提前做了 BFS，注意节点回退。

时间复杂度：

• 理论上应该也是 $\mathcal O(n^2m)$，但是因为此算法是在 Dinic 基础上优化的，所以实际上是会比 Dinic 快的，而且不算很难写。

模型

最小割

定义

定义一个有向图 $G=(V,E)$，的割为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V\ \backslash\ S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$，割的容量为 $c(S, T)=\sum_{u\in S, v\in T}c(u,v)$，最小割即 $c(S,T)_{\min}$。

算法

我们只要跑一遍最大流，即为最小割。

证明

见「最大流最小割定理」证明。

最大权闭合子图

定义

定义一个有向图 $G=(V,E)$ 的闭合子图 $G'=(V', E')$，满足对于 $∀(u,v)∈E$，若 $u∈V′$，则 $(u,v)\in E', v∈V′$。

最大权闭合子图即为对每个节点赋权值 $val$，所得到的最大 $\sum\limits_{p\in V'}val_p$。

算法

我们构造超级源点 $s$ 和汇点 $t$：

• 对于 $val_u > 0$，在新图上连边 $(s, u, val_u)$。
• 对于 $val_u\le 0$，在新图上连边 $(v, t, -val_v)$。
• 对于 $(u,v)\in E$，在新图上连边 $(u,v,+\infty)$。

所有正权值之和减最小割即是答案。

证明

感性证明一下，首先对于原图中的边 $(u,v,+\infty)$ 不可能在最小割里面，然后我们令若 $(s,u,val_u)$ 选到了最小割集，就代表不选 $u$；若 $(u, t,-val_u)$ 选到了最小割集，就代表选 $u$。选出来的图必定是闭合子图，因为对于一个没选的正权点 $u$，因为原图除去割集不联通，所以 $u$ 的所有负权后继与 $t$ 之间的边必然在割集内，也就是已经选到了最终权值中。

那怎么保证最大呢？最小割保证损失节点权值（定义为负）和与负权权值之和最小，自然闭合子图总权值最大。

最大密度子图

定义

定义一个图 $G=(V,E)$ 的密度为 $\dfrac {|E|} {|V|}$，则对于一个图 $G=(V,E)$，选出其一个子图 $G'=(V', E')$，使得密度最大，该图就是最大密度子图。

算法 1

我们考虑 0/1 分数规划，二分答案为 $g$，判断 $\dfrac {|E'|} {|V'|}\ge g$，即 $|E'|-g|V'|\ge 0$，于是我们只需要求 $\max\{|E'|-g|V'|\}$ 即可。这里注意二分范围为 $\left[\dfrac 1 n, m\right]$，$\epsilon=\dfrac{1}{n^2}$，即最小子图密度之差为 $\dfrac{1}{n^2}$。

然后又有选了边 $(u,v)$ 又一定要选点 $u,v$ 的限制，考虑最大权闭合子图的做法，建立超级源点 $s$ 和汇点 $t$：

• 对于表示边的点 $u$，在新图上连边 $(s, u, 1)$。
• 对于表示点的点 $u$，在新图上连边 $(u, t, g)$。
• 对于 $(u,v)\in$，在新图上连边 $(u,v,+\infty)$。

跑一遍最小割，令 $m\ge n$，二分次数为 $\log T\approx \log nm$，时间复杂度即为 $\mathcal O(m^3\log T)$。

证明

算法正确性显然，唯一需要注意点的是，最终答案不可能会出现只选表示点的点而不选与之相连的边，因为最优答案一定是原图的导出子图。

算法 2

证明 1 中说明了最终答案一定是一个导出子图，于是我们尝试在原图中找出最小割，割出一个导出子图。

首先按照算法一做一遍 0/1 分数规划，再将 $\max\{|E'|-g|V'|\}$ 转化为 $\min\{g|V'|-|E'|\}$，便于最小割，然后我们化一下式子：

$\begin{aligned}g|V'|-|E'|=&\sum\limits_{u\in V'}g-\left(\dfrac{\sum\limits_{u\in V'}deg_u-c(V',\overline{V'})}{2}\right)\\=&\dfrac 1 2\left(\sum\limits_{u\in V'}(2g-deg_u)+c(S,T)\right)\end{aligned}$

然后呢他有个神仙建图，从后往前推我不会，就先讲建图：

• 对于原图中的点 $u\in V$，在新图上连边 $(s,u,\Delta),(u,t,2g-deg_u+\Delta)$。
• 对于 $(u,v)\in E$，在新图上建边 $(u,v,1)$。

最后求最小割，关系式为 $|E'|-g|V'|=\dfrac{n\Delta-c(S,T)}{2}$，我们发现 $c(S,T)$ 和 $|E'|-g|V'|$ 是线性关系的，这就说明了最小割正确性，这个关系式在下面给出证明。其中 $\Delta$ 为偏移量，为了使边权非负，一般取 $\Delta = n$。

令 $m\ge n$，二分次数为 $\log T\approx \log nm$，时间复杂度即为 $\mathcal O(n^2m\log T)$。

证明

我们尝试推出 $c(S,T)$ 的本质，令 $V'=S\ \backslash\ \{s\}, \overline{V'}=T\ \backslash\ \{t\}$。

$\begin{aligned}c(S,T)&=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}(2g-deg_u+\Delta)+\sum\limits_{u\in V'}\sum\limits_{v\in \overline{V'}}c(u,v)\\ &=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}\left(2g+\Delta-\left(deg_u-\sum\limits_{v\in \overline{V'}}c(u,v)\right)\right)\\ &=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}\left(2g+\Delta-\sum\limits_{u\in V'}c(u,v)\right)\\ &=n\Delta+2g|V'|-2|E'|\end{aligned}$

然后移个项就得到了 $|E'|-g|V'|=\dfrac{n\Delta-c(S,T)}{2}$。

DAG 最小不相交 / 可相交路径覆盖

定义

在一个有向无环图中选出若干条不相交的路径，使得每个点都属于一条路径，这种方案称为不相交路径覆盖，最小路径覆盖即为路径数最小的方案。

同理，在一个有向无环图中选出若干条路径，使得每个点都至少属于一条路径，这种方案称为可相交路径覆盖，最小可相交覆盖即为路径条数最小的方案。

算法

• 不相交路径

对于每个点 $u\in V$，拆成入点 $u'$ 和出点 $u$，对于原图中 $(u,v)\in E$，在新图中建边 $(u,v',1)$，最终答案为总点数减去二分图 $G=(X,Y,E)$ 的最大匹配，其中出点集合为 $X$，入点集合为 $Y$，时间复杂度 $\mathcal O(m\sqrt n)$。

• 可相交路径

我们发现链可以相交，尝试着转化为链不相交的做法。

我们对原图做一次传递闭包，这样路径就可以跳着走，也就是如果两条链相交，可以选择一条链跳过相交点，这样就转化为了不相交做法。然后其实最终的方案可以和可相交路径方案对应的。时间复杂度 $\mathcal O(n^2(\dfrac n \omega+ \sqrt n))$。

对于更普遍的情况，我们指定某些点必须被覆盖，将所有点分成两层 $(0,u)$ 和 $(1,u)$，考虑以下建图方式：

• 对于必须被覆盖的点 $u$，连结 $(S, (0,u), 1)$ 和 $((1,u), T, 1)$
• 对于原图中的边 $(u,v)$ 在新图中连结 $((0, u), (1, v), +\infty)$；
• 对于所有点 $u$，连结 $((1, u), (0, u), +\infty)$

此时每条流量为 $1$ 的可行流都代表路径中的一条边，用覆盖点总数 - 最大流（最大边数）即是答案，这里将图分成两层的原因是防止出现 $S\overset{1}{\rightarrow}u\overset{1}{\rightarrow}t$ 的可行流。

证明

• 不相交路径

对于没有边的原图，答案显然是 $|V|$。而在新图中的每一条边 $(u,v')$，都代表原图中的路径合并，且因为求的是最大匹配，所以路径一定合法。于是答案就为点数减合并最大次数。

• 可相交路径

显然。

定理

最大流最小割定理

最大流等于最小割。

证明

upd：这玩意儿别看了，不知道当时自己在证什么鬼东西，有空补一下吧。

显然对于任意割一定大于等于任意流，特别的，有 $|f|_{\max}\le c(S, T)_{\min}$。

然后对于任意割 $c(S, T)=|f|$ 的情况，$f$ 此时一定是最大流，因为割的容量等于割的流量，相当于原图中已经没有增广路径，即最大流。又因 $|f|_{\max}\le c(S, T)_{\min}\le c(S, T)=|f|_{\max}$，即可得 $|f|_{\max}= c(S, T)_{\min}$。

Kőnig 定理

二分图最小点覆盖为最大匹配。

证明方式 1

我们考虑一个不存在增广路的最大匹配 $M$，并如下对点做标记：每次从一个未被匹配的左部点走交错路径，即从左往右走未匹配边，从右往左走匹配边，走过的所有点都打上标记。

其中对于所有未标记的左部点和标记的右部点为最小点覆盖集 $C$，我们将分两步证明。

点覆盖集合法

• 对于一条匹配边，一定是右端点先被标记，然后遍历左端点被标记，所以一条匹配边刚好有一个点属于点覆盖集。

• 对于一条未匹配边，必然至少有一个点属于点覆盖集，否则其左部点已被标记而右部点未被标记，显然这是不符合的。

点覆盖集最小

首先肯定有 $|C|\ge |M|$，因为每个匹配边至少需要一个单独的覆盖点。

然后证明 $|C|=|M|$：

• 对于右部被标记的点，必然被匹配，否则可以和左部过来的点匹配。

• 对于左部未被标记的点，必然被匹配，特殊情况为孤立点，此时交错路径退化为单点。

以上证明了如此构造点集一一对应匹配边，且为最小点覆盖集。

证明方式 2

考虑转化成最小割形式，令左部点集合为 $X$，右部点集合为 $Y$，则有 $(s,u,1), u\in L$，$(u,t,1),u\in R$，$(u,v,+\infty),u\in L, v\in R$。若得到最小割 $c(S,T)_{\min}$，这个最小割的容量即为 $|X\cap T|+|Y\cap S|$，因为不存在 $(u,v),u\in S, v\in T$ 被割。

于是我们构造点覆盖集合 $P=|X\cap T|\cup|Y\cap S|$，则所有 $(u,v),u\in S, v\in T$ 中 $u,v$ 至少有一个在 $P$ 中，否则不构成割集。所以最小割为最小点覆盖，又因最大匹配为最大流，最大流等于最小割，所以最小点覆盖为最大匹配。

霍尔定理

对于二分图 $G=(X,Y,E)$，$\forall S\subseteq X,|S|\le N(S) \Leftrightarrow$ 二分图具有完美匹配，当然，$|X|=|Y|$。

推广定理：$\forall S\subseteq X,m|S|\le N(S) \Leftrightarrow$ 二分图具有 $m$ 组完美匹配。

首先如果有完美匹配，必然有 $\forall S\subseteq X,|S|\le N(S)$，剩下的有两种方式证明：

证明方式 1

首先原图没有完美匹配但是满足以上条件，我们在左部图 $X$ 找到一个未被匹配的点，因为满足条件，所以右部与之相邻的点至少有一个且全部都一定被匹配，否则必定有更大的匹配。于是我们随便走到一个已经匹配的右部点，然后再走到相对应匹配的左部点，然后再随便找一个未走过的左部点，因为满足假设，我们最终一定停留在右部点。于是我们找到了一条增广路，不符合最大匹配。

证明方式 2

和 Kőnig 定理证明一样，如下连边：令左部点集合为 $X$，右部点集合为 $Y$，则有 $(s,u,1), u\in L$，$(u,t,1),u\in R$，$(u,v,+\infty),u\in L, v\in R$，并得到最小割 $c(S,T)_{\min}$。

我们假设满足 $\forall S\subseteq X,|S|\le N(S)$ 而二分图不具有完美匹配，则最大匹配 $|M|<|X|$，同时最小割 $c(S,T)_{\min} < |X|$。我们令 $L_1=S\cap X$，$L_2=X\ \backslash\ L_1$，$R_1=N(L_1)\cap Y$，则由 $L_2\cap R_1$ 一定在割集内，又因假设满足，所以有 $|L_1|\le |R_1|$。得到关系式 $c(S,T)_{\min}\ge |L_2\cap R_1|\ge|L_2\cap L_1|=|X|$，与假设矛盾，得证。

二分图 Vizing 定理

对于二分图 $G=(X,Y,E)$，对每一条边染色，使得每个点所连的边颜色各不相同，若满足条件的最小颜色数为 $\chi'(G)$，点的最大度数为 $\Delta(G) = \max\limits_{u\in V}deg_u$，则有 $\chi'(G)=\Delta (G)$。

证明

考虑构造性证明。令颜色集合为 $\{1,2,\dots, \Delta(G)\}$，对于每个点 $u$ 所连的边中，未被染的最小颜色编号为 $C_u$。

我们依次加入每一条边 $(u,v)$：

• 对于 $C_u=C_v$，将边 $(u,v)$ 染成 $C_u$ 颜色。
• 对于 $C_u\not=C_v$，令 $C_u< C_v$，则我们从 $v$ 开始找到一条增广路，颜色为交替 $C_u,C_v,C_u,\dots$，将整条路颜色翻转，并将 $(u,v)$ 染成 $C_u$ 颜色。

得证。

Dilworth 定理

在有向无环图中，最长反链等于最小链覆盖；其对偶定理为最长链等于最小反链覆盖。

注意：链不一定要连续，即链不等于路径

证明

对于原图，我们对其进行传递闭包，和求最小可相交路径覆盖一样，对于每个点 $u\in V$，拆成入点 $u'$ 和出点 $u$，对于原图中 $(u,v)\in E$，在新图中建边 $(u,v',1)$，最小链覆盖即为总点数减最大匹配。

还有一个结论：原图最长反链为最大独立集，以下证明：

对于原图中的任意一个点 $u$，在新图中 $u$ 和 $u'$ 中必然至少有一个点在最大独立集中，否则必然存在 $(a,u')$ 和 $(u, b)$ 两条边，使得 $a,b$ 都在最大独立集内，但如此原图便存在 $(a,b)$，故不成立，所以最大独立集满足对于每个点在新图中的入点和出点尽可能多。显然对于这些点可以形成一组反链，因为最大独立集保证没有前驱和后继与原点相连，且这组反链可以和原图对应。

然后因为由「其他定理 1」可得二分图最大匹配 = 最大独立集补集，所以最小链覆盖等于最长反链。

其他定理

二分图最大匹配 = 最小点覆盖 = 最大独立集补集

证明

我们发现点覆盖 $C$ 和独立集 $I$ 的定义恰好相反，即 $\forall (u,v)\in E,u\in C\vee v\in C$ 和 $\not\exists (u,v)\in E,u\in I\wedge v\in I$。所以最大独立集的补集，就保证了每条边都被覆盖。

根据「Kőnig 定理」，可得二分图最大匹配 = 最小点覆盖 = 最大独立集补集。

---

二分图最小边覆盖 = 点数减最大匹配

证明

很显然，对于最小边覆盖，我们希望一条边覆盖两个点的边数越多越好，即匹配数最大，于是最后总点数减去覆盖两个点的边即为最小边覆盖。

---

最大团 = 补图最大独立集

证明

最大独立集两两之间没有边，补图则两两之间有边，则为团。

$\bf\sf 0x02$ 最小费用最大流

算法

SSP（基于 EK）

算法过程：

• 用 SPFA 跑出原图最短路（忽略无流量的边）并在过程中记录找到的一条增广路，直到不存在增广路。

时间复杂度：$\mathcal O(nmf)$。

zkw 费用流

*Capacity Scaling

咕。

$\bf\sf 0x03$ 有源汇上下界最小 / 最小流

我们试图先找到一组可行流。对于无源汇，分别建出下界网络（$w=L$）和差网络（$w=R-L$），最终的可行流一定是下界网络和差网络的和。假设下界网络都是满流，但是流量不一定平衡，考虑在差网络上添加边。对于一个点 $u$ 在下界网络上的 $in_u$ 入流和 $out_u$ 出流，如果入流比出流大，则添加 $(S, u, in_u - out_u)$ 的边，这样保证出去此边差网络的出流比入流大 $in_u-out_u$，反过来同理。如果附加边没有流满，则没有可行流。对于有源汇，源汇流量一定不平衡，则在源汇之间连一条流量为 $\infty$ 的边即可。

我们找到一组可行流，则在差网络上从源到汇再跑一次最大流就是上下界最大流，同样的，从汇到原就是上下界最小流。