A6618. 「网络流 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} $。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
输入格式
第 $ 1 $ 行有 $ 2 $ 个正整数 $ m $ 和 $ n $，分别表示仓库数和零售商店数。接下来的一行中有 $ 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 $