网络流 EK (Edmond-Karp) 算法详解 求解最大流和费用流问题

前言

问题

有 $n$ 个城市,$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城,假设他们都有足够的钱去购买车票,那么最多有多少人能到达 $T$ 城?

思路

要使 $S$ 的人到达 $T$ ,首先要找到一条从 $S$ 到 $T$ 的通路(否则就到不了 $T$ 了)。显然,这条路最多只能通过其中供票最少的路的人数。在下面我们称这个最少的人数为 $k$ 。

然后这条路上的每条铁路都要减去 $k$ ,因为这条路中的每条铁路都通过了 $k$ 人,所以要全部减去 $k$ ,最终答案加上 $k$ 。

很明显,还有别的路可以通过,我们不断地找通路,并做以上的操作就应该可以找到最大流了。

但上述思路存在一个缺陷,如果找到的通路不是最优的,有其他的通路组合比其更优,那么答案就错误了。

在后文中,我们将会使用建反边的技巧解决这个问题。

定义

权值:一条边上最多的承载量(可以卖的票的数量)

增广路:从 $S$ 到 $T$ 的一条路,通过这条路可以使到达 $T$ 的总人数(流量)增加。

约定

本文使用的邻接表

EK 算法的实现

我们在图中不断找出增广路,然后将这条增广路上的每条边减去这条增广路上最小的权值,直到找不到增广路为止。

寻找增广路

我们可以通过 $BFS$ 来实现这一操作。在 $BFS$ 时记录一下当前增广路的路径,

EK 核心部分(不是最终的)

然后便是 EK 的核心了。不断找增广路,将路上权值减去,直到找不到增广路为止。

建反边

为什么要建反边

就这么结束了?EK 就这么简单?当然了,前文说过,但上述作法存在一个缺陷,如果找到的增广路组合不是最优的,有其他的增广路组合比其更优,那么答案就错误了。

所以我们建反边来巧妙解决这个问题。

如何建反边

对于每条正向边,建立一条与它相反的反向边,但边权为 $0$

我们在给正向边减少权值的同时,给反向边增加相同的权值。

反向边起到了一个标记的作用,使后来更优的解可以替换之前的不是最优的解。

(其实我也没完全理解反向边,以后再更吧,想了解可以看这篇博客

何时建反向边

在建正向边的同时建反向边。

注意

邻接表的 $top$ 要从 $1$ 开始,方便 EK 中对反向边的操作。

最终的 EK 核心部分

因为正向边和反向边的编号只相差 $1$ ,所以我们对于一条边 $x$ ,它的反向边是 $x\hat{}1$ 。(将邻接表初始时 top 设为 1 来保证此操作正确)

在给正向边减去权值的同时,给反向边加上权值,这也是唯一要改的一个地方(高亮处)。

邻接表定义的修改

核心代码

最终代码

洛谷 P3376【模板】网络最大流 为例

EK 算法的扩展

最小费用最大流 (费用流)

洛谷 P3381 【模板】最小费用最大流

将 $BFS$ 换成 $SPFA$ 即可。

代码不同的地方已经高亮标记。

 

暂无评论

发送评论


				
上一篇
下一篇