A2488. 运输问题
编程题
提高+/省选-
知识点
题目描述
$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}$ 。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
货物供需平衡，即$\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$ 个仓库有 $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}$。
输出格式
两行分别输出最小运输费用和最大运输费用。
输入输出样例
输入 #1
2 3 220 280 170 120 210 77 39 105 150 186 122
输出 #1
48500 69140
说明/提示
$1 \leq n, m \leq 100$