这种限制节点经过次数的估计就是网络流了
新建源汇s t
把一个点拆成两个,中间连接一条容量为经过次数的边
对于每一个蜥蜴,从s向这个点的入点连边,容量为1,表示有一条蜥蜴。对于每一个点可达的点从出点连边,容量正无穷,能跳出的向t连边,容量正无穷。跑最大流即可
dinic的时候不要忘记重置cur数组,一直死循环…………
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; //点ij为2*(c*(i-1)+j)入和2*(c*(i-1)+j)+1出 s=r*c*2+2 t=r*c*2+3 const int N=200010,INF=209999999; int to[N],from[N],fl[N],tail=1,pre[N],now[N],ans,d[N],vis[N],q[N*2],L,R,cur[N],r,c,di,tmp,g[50][50],xiyi; inline int o(int i,int j){return 2*(c*(i-1)+j);} void add(int u,int v,int f){ to[++tail]=v;pre[tail]=now[u];now[u]=tail;fl[tail]=f; to[++tail]=u;pre[tail]=now[v];now[v]=tail;fl[tail]=0; } bool bfs(int s,int t){ memset(vis,0,sizeof(vis)); L=R=0;q[++R]=s;vis[s]=1;d[s]=0; for(int x=q[++L];L<=R;x=q[++L]) for(int i=now[x];i;i=pre[i]) if(fl[i]>0 && !vis[to[i]]) d[to[i]]=d[x]+1,vis[to[i]]=1,q[++R]=to[i]; return vis[t]; } int dfs(int x,int t,int a){ if(x==t || a==0) return a; int flow=0,f; for(int &i=cur[x];i;i=pre[i]) if(d[to[i]]==d[x]+1 && (f=dfs(to[i],t,min(a,fl[i])))>0){ fl[i]-=f;fl[i^1]+=f;flow+=f;a-=f; if(a==0) break; } return flow; } int main(){ //freopen("1066.in","r",stdin);freopen("1066.out","w",stdout); scanf("%d%d%d\n",&r,&c,&di); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++) { g[i][j]=getchar()-'0'; if(g[i][j]) add(o(i,j),o(i,j)^1,g[i][j]); } getchar(); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(g[i][j]) for(int x=-di;x<=di;x++) for(int y=-di;y<=di;y++) if(abs(x)+abs(y)<=di && i+x>0 && i+x<=r && j+y>0 && j+y<=c && g[i+x][j+y] && ((i+x)!=i || (j+y)!=j)) add(o(i,j)^1,o(i+x,j+y),INF); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ tmp=getchar(); if(tmp=='L') xiyi++,add(2*r*c+2,o(i,j),1); } getchar(); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(g[i][j] && min(min(r+1-i,i),min(c+1-j,j)) <= di) add(o(i,j)+1,2*r*c+3,INF); while(bfs(2*r*c+2,2*r*c+3)) { for(int i=1;i<=2*r*c+3;i++) cur[i]=now[i]; ans+=dfs(2*r*c+2,2*r*c+3,INF); } ans=xiyi-ans; printf("%d",ans); return 0; }