标签:EK算法

1 篇文章

网络流 EK (Edmond-Karp) 算法详解 求解最大流和费用流问题
前言 问题 有 $n$ 个城市,$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城,假设他们都有足够的钱去购买车票,那么最多有多少人能到达 $T$ 城? 思路 要使 $S$ 的人到达 $T$ ,首先要找到一条从 $S$ 到 $T$ 的通路(否则就到不了 $T$ 了)。显然,这条路最多只能通过其…