学弟@lher在周末训练赛中出的题目的原题（这个人拿省选题来当作提高组模拟，太丧了。。。）
题意简析：看题目：）
解题思路：题目显然是最大流。
首先拆点将点权变为边权，然后按照题意对于所有有跳板的点向可以跳到的点连一条权值为inf的边，对于能够跳出地图边界的点，将它与汇点连一条权值为inf的边。对于有蜥蜴的点，从源点向这个点连一条权值为1的边，然后跑一次最大流，答案就是蜥蜴数－最大流。
AC代码：
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
#define inf 0x7fffffff
using namespace std;
struct zxy{
int next,to,v;
}edge[];
int n,m,d,head[],iter[],lev[],que[],cnt=,mz=;
bool b[][];
inline int getno(int x,int y){ return (x-)*m+y;}
inline int getdis(int x,int y,int a,int b){ return ceil(sqrt((x-a)*(x-a)+(y-b)*(y-b)));}
inline void ins(int x,int y,int l){edge[++cnt].next=head[x],head[x]=cnt,edge[cnt].to=y,edge[cnt].v=l;}
inline int in(){
int x=,f=;
char ch=getchar();
while(ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline bool bfs(int s,int e){
memset(lev,-,sizeof(lev));
int t=,h=;
que[]=s;
lev[s]=;
do{
h++;
int k=head[que[h]];
while(k){
if (lev[edge[k].to]==-&&edge[k].v){
lev[edge[k].to]=lev[que[h]]+;
que[++t]=edge[k].to;
}
k=edge[k].next;
}
}while(h<t);
return lev[e]!=-;
}
inline int dfs(int u,int v,int f){
if (u==v) return f;
int used=,k=head[u];
while(k){
if (edge[k].v&&lev[edge[k].to]==lev[u]+){
int w=dfs(edge[k].to,v,min(edge[k].v,f-used));
used+=w;
edge[k].v-=w;
edge[k^].v+=w;
if (used==f) return used;
}
k=edge[k].next;
}
return used;
}
int dinic(int s,int t){
int flow=;
while(bfs(s,t))
flow+=dfs(s,t,inf);
return flow;
}
void init(){
n=in(),m=in(),d=in();
for (int i=; i<=n; ++i){
for (int j=; j<=m; ++j){
int x=getchar()-'',no=getno(i,j);
if (x) ins(no,no+n*m,x),ins(no+n*m,no,),b[i][j]=;
}
getchar();
}
for (register int i=; i<=n; ++i){
for(register int j=; j<=m; ++j)
if (getchar()=='L') ++mz,ins(,getno(i,j),),ins(getno(i,j),,);
getchar();
}
for (register int i=; i<=n; ++i)
for (register int j=; j<=m; ++j)
if(b[i][j]){
if (i-d<||i+d>n||j-d<||j+d>m) ins(getno(i,j)+n*m,n*m*+,inf),ins(n*m*+,getno(i,j)+n*m,);
for (int k=(i-d<?:i-d); k<=(i+d>n?n:i+d); ++k)
for (int t=(j-d<?:j-d); t<=(j+d>m?m:j+d); ++t)
if (b[k][t]&&getdis(i,j,k,t)<=d&&(i!=k||j!=t))
ins(getno(i,j)+n*m,getno(k,t),inf),ins(getno(k,t),getno(i,j)+n*m,);
}
}
int main(){
init();
printf("%d",mz-dinic(,*n*m+));
return ;
}
本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:13960948839@163.com.