自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:38:05，当前版本为作者最后更新于2018-07-05 20:04:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题目大意

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

解题思路

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

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

如下图