

$17.$运输问题

题目

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}$。 试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。 两行分别输出最小运输费用和最大运输费用。

题解

其实和上面那个问题差不多，仓库放左边，商店放右边，$S$ 向左边连 $(a[i], 0)$的边(前面为流量，后面为费用，后同)，右边集合向 $T$ 连 $(b[j], 0)$的边。 第i个仓库向第j个商店连边 $(INF, c_{ij})$。 跑完一遍费用流后还要把费用取相反数来跑一遍，以求出最大花费。