火星探险问题

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

上一篇：[BZOJ1030] [JSOI2007]文本生成器（AC自动机 + DP）

下一篇：[HDU1403]Longest Common Substring（后缀数组）