「网络流 24 题17」运输问题

题目描述:

W 公司有 m 个仓库和 n  个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。

货物供需平衡，即

从第 i 个仓库运送每单位货物到第 j  个零售商店的费用为 cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

输入格式:

第 1 行有 2  个正整数 m  和 n ，分别表示仓库数和零售商店数。接下来的一行中有 m  个正整数 ai ，表示第 i 个仓库有 ai 个单位的货物。再接下来的一行中有 n 个正整数 bj ，表示第 j 个零售商店需要 bj 个单位的货物。接下来的 m 行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用 cij 。

输出格式:

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

样例输入:

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

样例输出:

48500
69140

提示:

1≤n,m≤100

时间限制: 1000ms
空间限制: 256MB

---