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

题目大意

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

解题思路

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

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

如下图

![博客地址]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long
struct node{int to,v,nxt;}e[N];int head[N],len;
void add(int x,int y,int c)
{
	e[++len]={y,c,head[x]};head[x]=len;
	e[++len]={x,0,head[y]};head[y]=len;	
}
int cur[N],d[N],st,ed;
bool find()
{
	memset(d,0,sizeof(d));d[st]=1;
	deque<int>q;q.push_back(st);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y]==0&&e[i].v)
			{
				d[y]=d[x]+1;
				q.push_back(y);
				if(y==ed)return 1;
			}
		}
	}
	return 0;
}
int flow(int x,int s)
{
	if(x==ed)return s;
	int ans=0;
	for(int i=cur[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		cur[x]=i;
		if(d[y]==d[x]+1&&e[i].v)
		{
			int sum=flow(y,min(e[i].v,s));
			e[i].v-=sum;
			e[i^1].v+=sum;
			ans+=sum;
			s-=sum;
			if(s==0)break;
		}
	}
	if(ans==0)d[x]=0;
	return ans;
}
int dinic()
{
	int ans=0;
	while(find())
	{
		memcpy(cur,head,sizeof(cur));
		ans+=flow(st,1e18);
	}
	return ans;
}
int n,m,k,a[110][110];
int getin(int x,int y){return ((x-1)*m+y)*2-1;}
int getout(int x,int y){return ((x-1)*m+y)*2;}
int dis(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
map<int,int>mp;
signed main()
{
	cin>>n>>m>>k;len=1,st=0,ed=n*m*2+1;
	for(int i=1;i<=n;i++)
	{
		string s;cin>>s;
		for(int j=1;j<=m;j++)a[i][j]=s[j-1]-'0';
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		add(getin(i,j),getout(i,j),a[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		for(int ii=0;ii<=n+1;ii++)for(int jj=0;jj<=m+1;jj++)
		{
			if(ii==i&&jj==j)continue;
			if(dis(i,j,ii,jj)<=k*k)
			{
				if(ii==0||ii==n+1||jj==0||jj==m+1)
				{
					if(mp[getout(i,j)])continue;mp[getout(i,j)]=1;
					add(getout(i,j),ed,1e18);
				}
				else add(getout(i,j),getin(ii,jj),1e18);
			}
		}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		string s;cin>>s;
		for(int j=0;j<m;j++)if(s[j]=='L')
			add(st,getin(i,j+1),1),sum++;
	}
	int ans=dinic();
	cout<<sum-ans;
	return 0;
}

https://blog.csdn.net/tenkuo/article/details/154640258