RYIP在线题库
首 页   >   习题练习   >   提交
Problem1556--运输问题

1556: 运输问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

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

【 Input 】

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

【 Output 】

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

【 Sample Input 】

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

【 Sample Output 】

48500
69140

【HINT】

1≤n,m≤100

【 Source/Category 】