1373: 「网络流 24 题」运输问题
[Creator : ]
Description
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}$。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
第 i 个仓库有 $a_i$ 个单位的货物；第 j 个零售商店需要 $b_j$ 个单位的货物。货物供需平衡，即 $\sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_j$。
从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 $c_{ij}$。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
Input
第 1 行有 2 个正整数 m 和 n，分别表示仓库数和零售商店数。
接下来的一行中有 m 个正整数 $a_i$，表示第 i 个仓库有 $a_i$ 个单位的货物。
再接下来的一行中有 n 个正整数 $b_j$，表示第 j 个零售商店需要 $b_j$ 个单位的货物。
接下来的 m 行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用 $c_{ij}$。
接下来的一行中有 m 个正整数 $a_i$，表示第 i 个仓库有 $a_i$ 个单位的货物。
再接下来的一行中有 n 个正整数 $b_j$，表示第 j 个零售商店需要 $b_j$ 个单位的货物。
接下来的 m 行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用 $c_{ij}$。
Output
两行分别输出最小运输费用和最大运输费用。
Constraints
$1 \leq n, m \leq 100$
Sample 1 Input
2 3
220 280
170 120 210
77 39 105
150 186 122
Sample 1 Output
48500
69140