9023: 运输问题

Memory Limit：128 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

W 公司有m个仓库和n 个零售商店。第i 个仓库有i a 个单位的货物；第j 个零售商店
需要bj个单位的货物。货物供需平衡，从第i 个仓库运送每单位货物到
第j 个零售商店的费用为ij c 。试设计一个将仓库中所有货物运送到零售商店的运输方案，
使总运输费用最少

对于给定的m 个仓库和n 个零售商店间运送货物的费用，计算最优运输方案和最差运
输方案。

Input

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

Output

程序运行结束时，将计算出的最少运输费用和最多运输费用输出到文件output.txt中。

Sample Input Copy 

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

Sample Output Copy 

48500
69140

加入题单

上一题 下一题 算法标签：