运输问题

题目来源

网络流 24 题

$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}$ 。

试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

第一行有两个正整数 $m, n(1\leq m, n\leq 100)$ ，分别表示仓库数和零售商店数。

接下来的一行中有 $m$ 个正整数 $a_i$ ，表示第 $i$ 个仓库有 $a_i$ 个单位的货物。

再接下来的一行中有 $n$ 个正整数 $b_j$ ，表示第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

接下来的 $m$ 行，每行有 $n$ 个整数，表示从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用 $c_{ij}(c_{i, j} \geq 1)$ 。

两行分别输出最小运输费用和最大运输费用。

保证答案不超过 $10^9$ 。

2 3
220 280
170 120 210
77 39 105
150 186 122

48500
69140