【网络流24题】运输问题

2014年3月7日1,6780

题目描述 Description

W 公司有m个仓库和n 个零售商店。第i 个仓库有ai 个单位的货物;第j 个零售商店
需要bj个单位的货物。货物供需平衡,即  sum(si)=sum(bj)
。从第i 个仓库运送每单位货物到
第j 个零售商店的费用为cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案,
使总运输费用最少。
编程任务:
对于给定的m 个仓库和n 个零售商店间运送货物的费用,计算最优运输方案和最差运输方案。

输入描述 Input Description

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

输出描述 Output Description

将计算出的最少运输费用和最多运输费用输出

样例输入 Sample Input

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

样例输出 Sample Output

48500
69140

题解

1、从S向每个Xi连一条容量为仓库中货物数量ai,费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi,费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大,费用为cij的有向边。

求最小费用最大流,最小费用流就是最少运费,求最大费用最大流,最大费用流就是最多运费。