[SCOI2007] 蜥蜴

题面

在一个 r 行 c 列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 1,蜥蜴的跳跃距离是 d,即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减 1(如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度为 1,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。

输入格式

输入第一行为三个整数 r,c,d,即地图的规模与最大跳跃距离。以下 r 行为石柱的初始状态,0 表示没有石柱,1~3 表示石柱的初始高度。以下 r 行为蜥蜴位置,“L”表示蜥蜴,“.”表示没有蜥蜴。

输出格式

输出仅一行,包含一个整数,即无法逃离的蜥蜴总数的最小值。

思路

挺裸的网络流,需要注意的是如何处理每个点的最多经过次数,对于每个点 $i$ 将其拆为两个点$x_i,y_i$,并连一条最大经过次数的边,将这两个点看做整体即可。

建图:

  • $S$ 到每个有蜥蜴的点 $x_i$ 建权值为 $1$ 的边
  • 能跳出边界的点 $y_i$ 向 $T$ 建权值为 $+ \infty$ 的边
  • $x_i$ 到 $y_i$ 建权值为 $i$ 的最多经过次数的边
  • 每个点 $y_i$ 向一步能到达的点 $x_i$ 建权值为 $+ \infty$ 的边

代码

 

暂无评论

发送评论


				
上一篇
下一篇