#765. #6011. 「网络流 24 题」运输问题

#6011. 「网络流 24 题」运输问题

题目描述

W 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 aia_i 个单位的货物;第 jj 个零售商店需要 bjb_j 个单位的货物。货物供需平衡,即 ∑i=1mai=∑j=1nbj\sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_j。从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 cijc_{ij}。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

输入格式

第 11 行有 22 个正整数 mm 和 nn,分别表示仓库数和零售商店数。接下来的一行中有 mm 个正整数 aia_i,表示第 ii 个仓库有 aia_i 个单位的货物。再接下来的一行中有 nn 个正整数 bjb_j,表示第 jj 个零售商店需要 bjb_j 个单位的货物。接下来的 mm 行,每行有 nn 个整数,表示从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用 cijc_{ij}。

输出格式

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

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

数据范围与提示

1≤n,m≤1001 \leq n, m \leq 100