网络流入门(一): Edmonds-Karp算法

例题:HDU 3549 – Flow Problem

最大流问题模型

水流要从一张有向图的一个点S(源点)流到一个点T(汇点),有向图中的第$i$条边的最大容量是$c_i$,求最大的水流量是多少。

几个概念

  • 残量:每条边的容量与流量之差,也就代表还可以被使用的容量
  • 增广路:一条从S到T的路,满足这条路是“可流的”,也即每条边的残量都是大于0的
  • 增广:找出增广路的最小容量,将增广路上的每条边减去这个值

算法思想

如果残量网络中存在增广路,则流量可以增大;否则,当前流就是最大流。我们要建立正向边和反向边,建反向边的目的是防止当前走的增广路不是目标中要走的增广路,所以我们可以把已经从正向边流出去的通过反向边流回来。

最大流问题中,容量和流量满足3个性质:

  • 流量一定不大于容量
  • 从$v_x$到$v_y$的流量与从$v_y$到$v_x$的流量相反
  • 除S和T外所有的流量代数和为0

EK算法的实质就是通过BFS找增广路,直到S-T断流为止,渐进时间复杂度$O(VE^2)$。

参考教程

例题题解(EK算法模板)

题面:HDU 3549 – Flow Problem

最小割最大流定理

在增广路算法结束时,满足$a_u>0$的节点$u$的几何看成$S$,令$T=V-S$,此时求到的流$f$是$s-t$最大流,$(S,T)$是$s-t$最小割,且最大流的值与最小割的容量相等。

说点什么

avatar
50
  Subscribe  
提醒