p4012专题

P4012 深海机器人问题 最小费用最大流

题目描述 深海资源考察探险队的潜艇将到达深海的海底进行科学考察。 潜艇内有多个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。 深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。 每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。 本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可