把每个点拆成2个点，两点之间连边的边权为石柱高度
新建虚拟源点$S$和汇点$T$
$S$向所有有蜥蜴的点连边，边权1
其他边都连$inf$
剩下就是裸的$dinic$辣
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define N 200005 inline int Min(int a,int b){return a<b?a:b;} inline int Abs(int a){return a<0?-a:a;} const int inf=1e8; char a[25][25]; int R,C,D,S,T,d[N],cur[N],tot; bool vis[N]; int cnt=1,hd[N],nxt[N],ed[N],poi[N],val[N]; queue <int> h; inline void adde(int x,int y,int v){ nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt, ed[x]=cnt, poi[cnt]=y, val[cnt]=v; } inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,0);} inline int id(int x,int y){return (x-1)*C+y;} bool Bfs(){ memset(vis,0,sizeof(vis)); h.push(S); vis[S]=1; while(!h.empty()){ int x=h.front(); h.pop(); for(int i=hd[x];i;i=nxt[i]){ int to=poi[i]; if(!vis[to]&&val[i]>0) vis[to]=1,d[to]=d[x]+1,h.push(to); } }return vis[T]; } int Dfs(int x,int a){ if(x==T||a==0) return a; int F=0,f; for(int &i=cur[x];i&&a;i=nxt[i]){ int to=poi[i]; if(d[to]==d[x]+1&&(f=(Dfs(to,Min(a,val[i]))))>0) F+=f,a-=f,val[i]-=f,val[i^1]+=f; }return F; } int dinic(){ int re=0; while(Bfs()){ for(int i=1;i<=T;++i) cur[i]=hd[i]; re+=Dfs(S,inf); }return re; } void draw(int x,int y){//向周围距离<=d的点连边 if(a[x][y]=='0') return ; int p=id(x,y); bool tt=1; link(p<<1,p<<1|1,a[x][y]-'0'); for(int i=x-D;i<=x+D;++i) for(int j=y-D;j<=y+D;++j){ if((i==x&&j==y)||Abs(x-i)+Abs(y-j)>D) continue; if(i>0&&i<=R&&j>0&&j<=C) link(p<<1|1,id(i,j)<<1,inf); else if(tt) link(p<<1|1,T,inf),tt=0; } } int main(){ scanf("%d%d%d",&R,&C,&D); S=R*C*2+2; T=S+1; for(int i=1;i<=R;++i) scanf("%s",a[i]+1); for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) draw(i,j); for(int i=1;i<=R;++i) scanf("%s",a[i]+1); for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) if(a[i][j]=='L') link(S,id(i,j)<<1,1),++tot; printf("%d",tot-dinic()); return 0; }