求无法逃离的蜥蜴总数的最小值就是求最多逃离的蜥蜴总数
所以显然考虑最大流，一个流量的路径就相当于一只蜥蜴逃离的路径
发现每个位置有一个最大经过次数，所以把每个位置拆成两个点$x,y$，$x$ 到 $y$ 连流量为最大经过次数的边
从源点向每个蜥蜴的初始位置的 $x$ 连一条流量为 $1$ 的边，表示初始时这些位置有蜥蜴
然后对于每一个位置 $u$， $dfs$ 找出所有走 $d$ 步以内能到的位置 $v$，然后从 $u$ 的 $y$ 点向 $v$ 的 $x$ 点连一条流量 $INF$ 的边，表示蜥蜴从 $u$ 跳到 $v$
注意 $dfs$ 判断一下到达边界的情况，有的话就往汇点连流量 $INF$ 的边
然后 总蜥蜴数 - 最大流 就是答案了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9+7,xx[4]={0,1,0,-1},yy[4]={1,0,-1,0}; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt=1; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } int dep[N],Fir[N],S,T; queue <int> Q; bool BFS() { for(int i=S;i<=T;i++) Fir[i]=fir[i],dep[i]=0; dep[S]=1; Q.push(S); int x; while(!Q.empty()) { x=Q.front(); Q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; Q.push(v); } } return dep[T]>0; } int DFS(int x,int mxfl) { if(x==T||!mxfl) return mxfl; int fl=0,res; for(int &i=Fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1||!val[i]) continue; if( res=DFS(v,min(mxfl,val[i])) ) { mxfl-=res; fl+=res; val[i]-=res; val[i^1]+=res; if(!mxfl) break; } } return fl; } inline int Dinic() { int res=0; while(BFS()) res+=DFS(S,INF); return res; } //以上网络流模板 int n,m,D,nm,id[107][107],ans;//id存每个位置的x, y=x+n*m bool vis[107][107];//dfs时防止重复走 int mp[107][107];//mp存每个位置的限制 inline void dfs(int s,int x,int y,int stp)//起点，坐标x,y，走了stp步 { if(stp==D) return; vis[x][y]=1; for(int k=0;k<4;k++) { int tx=x+xx[k],ty=y+yy[k]; if(vis[tx][ty]) continue; if(tx<1||tx>n||ty<1||ty>m) { add(nm+s,T,INF); continue; }//特判出界 if(mp[tx][ty]) add(nm+s,id[tx][ty],INF); dfs(s,tx,ty,stp+1); } vis[x][y]=0; } int main() { int a; char c[107]; n=read(),m=read(),D=read(); S=0,T=(n*m<<1)+1; nm=n*m; for(int i=1;i<=n;i++) { scanf("%s",c+1); for(int j=1;j<=m;j++) { id[i][j]=(i-1)*m+j; mp[i][j]=a=c[j]-'0'; if(a) add(id[i][j],nm+id[i][j],a);//每个位置的x向y连边 } } for(int i=1;i<=n;i++) { scanf("%s",c+1); for(int j=1;j<=m;j++) { if(mp[i][j]) dfs(id[i][j],i,j,0); if(c[j]=='L') add(S,id[i][j],1),ans++;//初始蜥蜴 } } printf("%d ",ans-Dinic()); return 0; }