题解 P2472 【[SCOI2007]蜥蜴】

· · 题解

这里提供一下题目大意和解题思路（其实主要还是那张图）

题目大意

在一个n\times m的矩阵中，每个格子都有一定的高度，当高度为0时表示该格子不存在，现在这个矩阵中有若干只蜥蜴，每只蜥蜴跳到格子上时，该格子的高度会减一，每只蜥蜴可以跳跃直线距离不大于D的长度，问最少有几只蜥蜴无法逃离

解题思路

最少有几只蜥蜴无法逃离=蜥蜴总数-最多有几只蜥蜴能逃离

对于每个点，我们进行拆点，将其拆分为入点和出点，显然它们之间的容量为该格子高度（最多能跳h[i][j]只蜥蜴），对于可以跳出矩阵的点，将它们的出点与汇点连边，容量为无穷大（允许所有蜥蜴逃离），对于所有起点，我们将源点和它们的入点连边，容量为1（每个点上至多有一只蜥蜴），最后跑最大流，然后用蜥蜴数减去最大流即为题目答案所求

如下图