首页 > 题解 > 网络流24题之十七 运输问题

网络流24题之十七 运输问题

填坑

地址:cv1914

images

样例输入 Sample Input

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

样例输出 Sample Output

48500
69140

模型

费用流问题。

实现

把所有仓库看做二分图中顶点Xi,所有零售商店看做二分图中顶点Yi,建立附加源S汇T。

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

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

分析

把每个仓库想象成一个中转站,由源点运来ai单位货物,运费为0,每个商店也为一个中转站,运向目标汇点bi单位货物。每个仓库和零售商店之间有一条道路,容量为无穷大,费用为单位运费cij。求从源点到汇点的费用流,就是运费。

代码

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×