首页 > 题解 > 网络流24题之二十 深海机器人问题

网络流24题之二十 深海机器人问题

填坑

地址:cv1917

images

images

images

样例输入 Sample Input

1 1
2 2
1 2
3 4
5 6
7 2
8 10
9 3
2 0 0
2 2 2

样例输出 Sample Output

42

模型

最大费用最大流问题。

实现

把网格中每个位置抽象成网络中一个节点,建立附加源S汇T。

1、对于每个顶点i,j为i东边或南边相邻的一个节点,连接节点i与节点j一条容量为1,费用为该边价值的有向边。
2、对于每个顶点i,j为i东边或南边相邻的一个节点,连接节点i与节点j一条容量为无穷大,费用为0的有向边。
3、从S到每个出发点i连接一条容量为该点出发的机器人数量,费用为0的有向边。
4、从每个目标点i到T连接一条容量为可以到达该点的机器人数量,费用为0的有向边。

求最大费用最大流,最大费用流值就采集到的生物标本的最高总价值。

分析

这个问题可以看做是多出发点和目的地的网络运输问题。每条边的价值只能计算一次,容量限制要设为1。同时还将要连接上容量不限,费用为0的重边。由于“多个深海机器人可以在同一时间占据同一位置”,所以不需限制点的流量,直接求费用流即可。

代码

 

 


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

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

×