BZOJ 1066, 蜥蜴

2019-11-06 07:51:09

字体：大中小

来源：转载

供稿：网友

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;}

上一篇：udp改变缓冲区大小

下一篇：C语言的那些小秘密之volatile

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注