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

填坑

此题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，“多个探测车可以在同一时间占据同一位置”，非障碍点内部要有一条容量为无穷大的边。直接求费用流即可。