【OI之路】03图论算法-5网络流

网络流类似流水问题
难点就是构图与建边
也有各种变例

有个不错的入门教程

网络流-纳米黑客
PDF

最大流解决方案

Edmond-Karp 理论上界是 $nm^2$ ,但通常可以解决$10^3$ ~ $10^4$ 的规模

EK的缺点主要是,每次只找出一条增广路
Dinic算法试图改进这一点

  1. 通过bfs得出残余网络中的分层图(显然是一个dag)
  2. 通过dfs得出增广路,回溯时更新流量
    3.
    理论上界是 $n^2m$ ,但通常可以解决$10^4$ ~ $10^5$ 的规模

特别地,对于二分图匹配,时间复杂度可以达到$O(m \sqrt n)$

最大流练习

题目直观版:Tag-网络流

最大流:
Caioj1115 Poj1273
Drainage Ditches
Caioj1116 Poj3281
Dining
Caioj1117 Poj2455 Bzoj1733
Secret Milking Machine
Caioj1118 Poj2112
Optimal Milking
Caioj1119 Poj2391
Ombrophobic Bovines
Caioj1120 Poj3189
Steady Cow Assignment

最小(割的容量)=最大流
很规范的PPT
最小割:
Bzoj1934 Bzoj2768
善意的投票&冠军调查
Bzoj1001
狼抓兔子

51nod-1299
师兄刚好给我看这题,但这道题我就不做了,
好像正解不是最小割,会超时一半,我就说说最小割部分分的思路:
原图中每个点拆为左点和右点,原图的边边权为无限,左点和右点之间的边边权为1
从源点到犯人的左点连条边,从出口点的右点到汇点连条边,跑一遍最大流就是答案

费用流

最小费用最大流是指满足源点流出的流量最大时,总费用最小的一个网络,模板都是基于此。
最大费用最大流则是将所有的费用取负,然后再跑一遍最小费用最大流,
将最终的最小费用取负就是最大流量下的最大费用了。
最大费用可行流关注的是费用而非流量是否最大,暂时不会
最小费用可行流没有意义

资料:窝嘞割草
本质上其实就是把EK中bfs换成能处理边权的spfa
(因为dinic无法处理,所以只有EK的衍生版)

题目:
Tag-费用流

至于zkw费用流……
jzq233jzq
zkw

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/5c7c.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%