蜥蜴
第一道紫题，写篇题解纪念一下
对于每根石柱，采取一分为二的想法，即把一个点分为两个点（可抽象为石柱底部到顶部，自己画个图理解一下吧），其连线容量限制为石柱高度(从底向顶连)。
首先，超级源点向每个蜥蜴所在石柱的底部连一条为1的边
然后，找到能跳出去的石柱，顶端向超级汇点连一条为inf的边
前两步很容易，下一步有点难理解，自己画图理解一下，我懒得上传图片了
对于地图内任意两个石柱，如果间距小于d，就将其中一根石柱的顶部与另一根石柱的底部相连，其连线容量为inf。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int inf=1e9;
int i,j,n,m,s,t,ans,dis,tot,d[10005];
struct node{
int next,to,w;
}a[500000];
int cnt=1,head[10005],cur[10005];
int k,x[10000],y[10000],hi[1000][1000],zn[1000][1000];
char s1[201][201],s2[201][201];
queue <int> q;
void add(int x,int y,int dis)
{
a[++cnt].next=head[x];
a[cnt].to=y;
a[cnt].w=dis;
head[x]=cnt;
}
bool bfs(int s,int t)
{
memset(d,0x7f,sizeof(d));
while(!q.empty()) q.pop();
for(int i=0;i<=2*k+1;i++) cur[i]=head[i];
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(d[v]>inf&&a[i].w)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
if(d[t]<inf) return true;
else return false;
}
int dfs(int now,int t,int limit)
{
if(!limit||now==t) return limit;
int flow=0,f;
for(int i=cur[now];i;i=a[i].next)
{
cur[now]=i;
int v=a[i].to;
if(d[v]==d[now]+1&&a[i].w&&(f=dfs(v,t,min(limit,a[i].w))))
{
flow+=f;
limit-=f;
a[i].w-=f;
a[i^1].w+=f;
if(!limit) break;
}
}
return flow;
}
int main()
{
scanf("%d%d%d",&n,&m,&dis);
for(i=1;i<=n;i++)
{
scanf("%s",s1[i]);
for(j=0;j<m;j++)
{
hi[i][j+1]=s1[i][j]-48;//记录高度
if(hi[i][j+1]!=0)
k++,x[k]=i,y[k]=j+1,zn[i][j+1]=k;//k是当前石柱编号，zn记录编号，x,y记录位置
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(hi[i][j]!=0)
{
if(i<=dis||i+dis>n||j<=dis||j+dis>m)
add(zn[i][j]+k,2*k+1,inf),add(2*k+1,zn[i][j]+k);//2*k+1为超级汇点，可以跳出去就连边
}
for(i=1;i<=n;i++)
{
scanf("%s",s2[i]);
for(j=0;j<m;j++)
if(s2[i][j]=='L') //如果有蜥蜴，向石柱底部连边
{
int v=zn[i][j+1];
tot++;
add(0,v,1);
add(v,0,0);
}
}
for(i=1;i<=k;i++)
add(i,i+k,hi[x[i]][y[i]]),add(i+k,i,0);//石柱底部向顶部连边
for(i=1;i<=k;i++)
for(j=1;j<=k;j++)
{
if(i==j) continue;
if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=dis*dis)
//两根石柱的距离小于dis，一根的顶部向另一根的底部连边
add(i+k,j,inf),add(j,i+k,0);
}
s=0;t=2*k+1;
while(bfs(s,t)) ans+=dfs(s,t,inf);//网络流模板，不解释
printf("%d",tot-ans); //总蜥蜴数减去能跳出去的
return 0;
}