最大流简陋小记
起因是某次模拟考出现二分图最大匹配，但是故意卡掉匈牙利只能用网络流，于是快速学了下。
超级简陋，之后或许会重写？
基本概念
想象一座城市的水网：
- 网络：水网。
- 源点
s ：有源源不断地水，相当于水厂。 - 汇点
t ：所有水最终汇入此处，相当于你家。 - 边：一条有向边，也可称弧。
- 容量
e_c ：水管每单位时间可经过的水的上界。 - 流量
e_f ：水管每单位时间内可经过的水。之后会用函数f 的形式描述。 - 残留容量
e_r ：e_r=e_c-e_f ，水管还可继续流经的水量。 - 容量网络：边带容量的网络。类比有流量 / 残量网络。
- 网络的流量：
\sum f(s,x) 或\sum f(x,t) 。你家总共收到的水。流量的函数表示 / 性质
- 容量限制：
e_f\le e_c 。 - 流量守恒：
\sum f(u,v)=0 ，也可写为\sum f(x,u) = \sum f(u,y) 。有多少水流进来，就有多少水流出去。 - 斜对称性：
f(u,v) = -f(v,u) ，比较难理解但是很重要。最大流
求如何分配水流，使得网络的流量最大？我们将这样分配下的流量网络称作最大流网络。
增广路定理
- 增广路：在残量网络上一条从
s 到t 的路径，满足边的残量均>0 。 - 增广路定理：该网络是最大流网络，当且仅当不存在增广路。
简单理解为：否则可以走这条增广路使得流量增加。
EK 算法
一种容易想到的思路是：建出残量网络，然后不断走增广路。
该算法流程如下：
-
初始化残量网络：
r(u,v)=c(u,v),r(v,u)=0 。 -
-
设增广路上最小残量是
minr ，则对其路上的所有e(u,v) 都：r(u,v)-minr ，为了满足斜对称性对其反边r(v,u)+minr 。答案增加minr 。 -
重复
2,3 直到不存在增广路。
比较难理解的是反边（因为增广路可以由反边构成！），而且对边操作后其反边的残量还会增加，比较玄幻。
可以理解为正边的反悔标记。每次对
而对于
EK
dinic 算法
发现