PRoblem
传送门
Mean
参见题目描述。
Analysis
网络流的难点就在于构图……
将一根石柱拆成上端和下端两个点并连边，容量为石柱高。
从源点像一根有蜥蜴的石柱上端连边，容量为1。
再从每一根能跳出地图的石柱下端向汇点连边，容量为INF。
蒟蒻真的做题无力啊……
Code
#include<cstdio>
#include<cstring>
const int N=25,M=805,V=55005,INF=~0U>>1;
int R,C,D,s,t,sum,ans,cnt,ed=1,l,r,f[N][N],id[N][N][2],u[V],v[V],c[V],nxt[V],g[M],cur[M],q[M],d[M];
bool vis[M];
int dis(int x,int y,int a,int b){return (x-a)*(x-a)+(y-b)*(y-b);}
int min(int a,int b){return a<b?a:b;}
void add(int x,int y,int z){
u[++ed]=x,v[ed]=y,c[ed]=z,nxt[ed]=g[x],g[x]=ed;
u[++ed]=y,v[ed]=x,c[ed]=0,nxt[ed]=g[y],g[y]=ed;
}
bool bfs(){
memset(vis,0,sizeof(vis));
vis[l=r=0]=1;
while(l<=r){
int x=q[l++];
for(int i=g[x];i;i=nxt[i]) if(!vis[v[i]] && c[i]){
q[++r]=v[i];
d[v[i]]=d[x]+1;
vis[v[i]]=1;
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t || !a) return a;
int flow=0,f;
for(int &i=cur[x];i;i=nxt[i]) if(d[v[i]]==d[x]+1 && (f=dfs(v[i],min(a,c[i])))>0){
c[i]-=f;
c[i^1]+=f;
flow+=f;
a-=f;
if(!a) break;
}
return flow;
}
int main(){
scanf("%d%d%d",&R,&C,&D);
for(int i=1;i<=R;i++){
getchar();
for(int j=1;j<=C;j++) if(f[i][j]=getchar()-'0') add(id[i][j][0]=++cnt,id[i][j][1]=++cnt,f[i][j]);
}
t=++cnt;
for(int i=1;i<=R;i++){
getchar();
for(int j=1;j<=C;j++) if(getchar()!='.'){add(s,id[i][j][0],1);sum++;}
}
for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) if(f[i][j]){
if(i<=D || R-i<D || j<=D || C-j<D) add(id[i][j][1],t,INF);
for(int x=1;x<=R;x++) for(int y=1;y<=C;y++) if((x!=i || y!=j) && dis(x,y,i,j)<=D*D) add(id[i][j][1],id[x][y][0],INF);
}
while(bfs()){
for(int i=0;i<=t;i++) cur[i]=g[i];
ans+=dfs(s,INF);
}
printf("%d",sum-ans);
return 0;
}
