最大流
增广路算法
从流量为0的容许流开始 不断寻找增流路径
增加容许流流量 直到无法增加
Ford-Fulkerson 标号算法
记录$v_e=c_e-f_e$为一条边的剩余容量
定义残量网络 对于每条边$e=(u,v)$,其边权为$v_e$,并对其增加一条反向边$e^,=(v,u)$,边权为$f_e$
每次在残量网络中找一条S到T的路径，边权均不为0
则这条路径成为增广路
若增广路上存在反向边 则相当于反悔
自己画图结合图理解
qwq
EK算法
FF算法复杂度与边权有关
若差距悬殊 则效率极低
引入EK算法
每次找一条边数最少的增广路
寻找路径时BFS即可
可以证明复杂度与边容量无关
且增广路条数不超过$m(n+2)/2$
证明
显而易见
DINIC算法
将残量网络分层 求出$dis_i$
考虑所以满足不为0且$dis_i+1=dis_j$的边$e=(i,j)$
一定在这些边组成的DAG上S到T路径均为最短路
在该DAG上DFS 即可一次求出多条增广路
当前弧优化
使用一个指针确认当前点可用于增广的第一条边