传送门
【题目分析】
令人智熄的字符串读入操作。。。。。在BZOJ上过了然后氵谷全T？emmm。。。。。。
网络流的题难点就在于建图，这道题还是比较明显，首先每个点还是要拆点限制流量，上限设为石柱高度表示最多可以跳过这么多蜥蜴。
建立一个起点s和终点t，每个有蜥蜴的石柱对应的入点就和起点s连接，s与入点间的弧容量为1(含义是该石柱只能有一个蜥蜴，如果容量大于1，就有可能在跑最大流时出现一个石柱有多个蜥蜴的情况)，每个与边界距离足够近的石柱对应的出点和终点t连接，t与出点间的弧容量为INF，这样t与出点间的弧容量不会影响到结果，此题的图就建立完成了，再跑一遍最大流，最大流等于能逃脱的蜥蜴数量，输出时用总蜥蜴数减去能逃脱的蜥蜴数即可。
【代码~】
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;
const int MAXM=5e5+10;
const int INF=0x3f3f3f3f;
int n,m,cnt,s,t,mind,ans;
int head[MAXN],cur[MAXN],depth[MAXN];
int nxt[MAXM],to[MAXM],w[MAXM];
int mx[MAXN],my[MAXN],tot;
char x;
int Read()
{
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void Add(int x,int y,int z)
{
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt]=z;
cnt++;
}
void add(int x,int y,int z)
{
Add(x,y,z);
Add(y,x,0);
}
bool bfs()
{
queue<int> q;
memset(depth,0,sizeof(depth));
depth[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(!depth[v]&&w[i])
{
depth[v]=depth[u]+1;
q.push(v);
}
}
}
return depth[t]!=0;
}
int dfs(int u,int dist)
{
if(u==t)
return dist;
for(int &i=cur[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(depth[v]==depth[u]+1&&w[i])
{
int di=dfs(v,min(w[i],dist));
if(di>0)
{
w[i]-=di;
w[i^1]+=di;
return di;
}
}
}
return 0;
}
int dinic()
{
int ans=0;
while(bfs())
{
for(int i=s;i<=t;++i)
cur[i]=head[i];
while(int d=dfs(s,INF))
ans+=d;
}
return ans;
}
int dist(int x1,int y1,int x2,int y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int zh(int x,int y)
{
return (x-1)*m+y;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d\n",&n,&m,&mind);
s=0,t=n*m*2+1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>x;
if(x!='0')
{
add(zh(i,j),zh(i,j)+n*m,x-'0');
if(i<=mind||j<=mind||i+mind>n||j+mind>m)
add(zh(i,j)+n*m,t,INF);
tot++;
mx[tot]=i,my[tot]=j;
}
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>x;
if(x=='L')
ans++,add(s,zh(i,j),1);
}
}
for(int i=1;i<=tot;++i)
for(int j=1;j<=tot;++j)
if(i!=j)
{
if(dist(mx[i],my[i],mx[j],my[j])<=mind*mind)
add(zh(mx[i],my[i])+n*m,zh(mx[j],my[j]),INF);
}
cout<<ans-dinic();
return 0;
}
