网络流/二分图相关笔记(干货篇)

备忘 : 随机化一般图最大匹配

请配合 : 网络流/二分图相关笔记(应用篇) 食用

网络流作为一个玄学算法,其题目难度主要在构图上。

至于网络流本身的算法模板,(如果不精细要求复杂度的话)实现起来难度不大。

在此就不多讲模板的实现了,只简单讲讲我对网络流的理解,如果模板部分看不懂建议先找别的文章学习。

本文内容:

主要是模板。

网络流模型的构建

性质 : 流量守恒,反对称性,流量范围

基本结构 : 增广路,反向边,残量网络

与线性规划的关系 (咕咕咕)

几种常见最大流算法以及复杂度说明

Ford-Fulkerson

Edmonds–Karp

Dinic (包括一些奇怪的优化)

关于网络流/二分图的常见模型

二分图 : 匹配 , 最小点覆盖 , 独立集 , Hall定理

最小路径覆盖

闭合子图问题

偏序集 : 最小连覆盖 , 最长反链

费用流

EK费用流

zkw费用流

消圈费用流 (咕咕咕)

带有负环的费用流

费用流与凸性的关系 (咕咕咕)

上下界网络流

上下界无源汇可行流

上下界有源汇可行流

上下界有源汇最大流

上下界有源汇最小流

上下界有源汇费用可行流

上下界无源汇费用可行流

最小割树及部分证明

我们这一节的目标就是切掉 P3376 【模板】网络最大流 ,并且要尽量跑得快些。

想象一些有向的水管,每个水管都有固定的流量上限,有源点可以出水,有汇点可以收水,问汇点单位时间最多可以收到多少水。

设$f[u,v]$为$u$向$v$流的流量,$c[u,v]$为$u\rightarrow v$的容量限制,$S$为源点,$T$为汇点。

$f[u,v]