洛谷P4015 费用流算法

阅读量：

运输问题

$W$ 公司拥有 $m$ 个仓储设施以及 $n$ 个零售网点。其中，第 $i$ 个仓储设施储存有 $a_i$ 单位的商品；而第 $j$ 个零售网点则需要获取 $b_j$ 单位的商品。

在该物流系统中，商品的总供给量与总需求量保持一致，即满足 $\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$ 的条件。

将第 $i$ 个仓库中的每单位商品运送至第 $j$ 个零售商店所产生的运输成本为 $c_{ij}$ 。

现需制定一套运输策略，将所有仓储点的商品配送至各个零售网点，目标是实现整体运输成本的最小化。

第 $1$ 行包含 $2$ 个正整数 $m$ 和 $n$ ，分别用于表示仓库的数量以及零售商店的数量。

随后的一行中包含 $m$ 个正整数 $a_i$ ，用以描述第 $i$ 个仓库所拥有的货物单位数量。

再接下来的一行中包含 $n$ 个正整数 $b_j$ ，用于表示第 $j$ 个零售商店所需的货物单位数量。

之后的 $m$ 行中，每一行均包含 $n$ 个整数，这些数值代表从第 $i$ 个仓库向第 $j$ 个零售商店运输每单位货物所需支付的费用 $c_{ij}$ 。