首页 > 题解 > 网络流24题之二十三 火星探险问题

网络流24题之二十三 火星探险问题

填坑

images

images

images

此题oj上全无SPJ,无法提交

模型

最大费用最大流问题。

实现

把网格中每个位置拆分成网络中两个节点<i.a>,<i.b>,建立附加源S汇T。

1、对于每个顶点i,j为i东边或南边相邻的一个节点,连接节点<i.b>与节点<j.a>一条容量为无穷大,费用为0的有向边。
2、从每个石块顶点<i.a>到<i.b>连接一条容量为1,费用为1的有向边。
3、从每个非障碍顶点<i.a>到<i.b>连接一条容量为无穷大,费用为0的有向边。
4、从S到登陆舱位置<(1,1),a>连接一条容量为探测车数,费用为0的有向边。
5、从传送器位置<(P,Q),a>到T连接一条容量为探测车数,费用为0的有向边。

求最大费用最大流,最大费用流值就是最多的岩石标本的数量。所有满流边构成多条满流路径,每条从S到T的路径就是一个探测车的路径。

分析

这个问题可以看做是出发点和目的地唯一的网络运输问题。每个石块点的价值只能计算一次,所以容量限制要设为1,“多个探测车可以在同一时间占据同一位置”,非障碍点内部要有一条容量为无穷大的边。直接求费用流即可。


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

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

×