网络流基础知识

1.流函数
给定一个网络\(G=(V,E)\),每条边有一个c(x,y)
流函数满足:\(f(x,y)\):
\(f(x,y) \le c(x,y)\) 容量限制
\(f(x,y)=-f(y,x)\) 斜对称
\(\sum f(u,x)=\sum f(x,v)\) 流量守恒

2. EK
3. 增广路 存在路径S->T, 任意一条边剩余容量>0
   不断寻找增广路 更新当前边容量和反向边容量 知道不存在增广路
   反向边相当于反悔容量

3.Dinic
多路增广 每次选择发现流量没有用完后就再去增广 每次只在分层图上增广
即先考虑能直接到达T的边 再考虑层之间的边

最小割=最大流
残量网络的点和其他点之间的边构成最小割

费用流
bfs找增广路改成用spfa找增广路