EK (Edmond-Karp) 算法 学习笔记

什么是EK算法

EK (Edmond-Karp) 算法,说白了就是求最大流/费用流之类的问题的算法。

什么是最大流

定义

带权的有向图$G=(V,E)$,满足以下条件,则称为网络流图$(flow network)$:
  1. 仅有一个入度为$0$的顶点$s$,称$s$为源点。
  2. 仅有一个出度为$0$的顶点$t$,称$t$为汇点。
  3. 每条边的权值都为非负数,称为该边的容量,记作$c(i,j)$。
  4. 通过容量网络$G$中每条弧$< u,v>$上的实际流量(简称流量),记为$f(u,v)$,称为弧的流量。
简单来说就是水流从一个源点$s$通过很多路径,经过很多点,到达汇点$t$,问你最多能有多少水能够到达$t$点。 从$s$到$t$经过若干个点,若干条边,每一条边的水流都不能超过边权值(可以小于等于但不能大于) (由于是来学EK算法的,最大流什么的详细解读就不说了)

例题

Luogu P3376 【模板】网络最大流

题意

给出一个网络图,以及其源点和汇点,求出其网络最大流。

思路

这是最大流的模板题,请往下阅读。

增广路

增广路定义

增广路是指从源点$s$到汇点$t$的一条路,流过这条路,可以使得当前的流可以增加。

如何求增广路

其实就是从源点$s$开始$bfs$即可,到达汇点$t$时,然后找到这个路径的权值的最小的边,然后把路径上的每一条边减去这个最小值即可。

Code

寻找增广路

定义

EK算法核心(你别急,我还没说完)

这样很明显是错误的。。。

反向边

为什么要建反边

为什么不建反边(逃: 非常显然,如果第一次流错了使其无法得到最大流怎么办? 就比如这张图:
然而$bfs$沙雕的选了上面一条路怎么办。。。 所以这时候就需要反向边出场了 一开始用反向边建一个比边权为$0$的边。就像这样↓
然后每次$bfs$以后给相应的反边加上流量,正边减去流量。

Code

回归例题

所以这道最大流的模板题代码:

Code

EK算法拓展

费用流问题

Luogu P3381 【模板】最小费用最大流

Code

评论

  1. I will immediately seize your rss feed as I can’t to find your
    e-mail subscription link or newsletter service.
    Do you’ve any? Please permit me recognise in order that I could subscribe.

    Thanks. http://www.epowersports.com/media/js/netsoltrademark.php?d=microscan.net%2F__media__%2Fjs%2Fnetsoltrademark.php%3Fd%3D918.network%2Fcasino-games%2F76-sky777

    5月前
    2019-4-20 22:06:40

发送评论


				
上一篇
下一篇