本文共 2880 字，大约阅读时间需要 9 分钟。
二分答案，网络流判断
将每个门拆点，每个人连向每个门的dis~当前解
然后跑最大流，如果等于人数，即为可行解
#include #include #include #include #include #include #define pa pair #define N 405#define inf 0x7fffffffusing namespace std;int n,m,p,per=0,door=0,S,T;pa pos[N];char s[25],a[25][25];map pp,dd;int h,t,xx[N],yy[N];int dis[N][N];bool bo[N][N];int e=2,head[50005];struct edge{ int u,v,f,next;}ed[8000005];void add(int u,int v,int f){ ed[e].u=u; ed[e].v=v; ed[e].f=f; ed[e].next=head[u]; head[u]=e++; ed[e].u=v; ed[e].v=u; ed[e].f=0; ed[e].next=head[v]; head[v]=e++;}void bfs(int x,int y){ memset(bo,0,sizeof bo); h=t=1; xx[1]=x; yy[1]=y; int now=dd[pa(x,y)]; while(h<=t){ int tx=xx[h],ty=yy[h++]; if(tx-1>0&&a[tx-1][ty]=='.'&&!bo[tx-1][ty]){ dis[pp[pa(tx-1,ty)]][now]=(tx==x&&ty==y?1:dis[pp[pa(tx,ty)]][now]+1); xx[++t]=tx-1; yy[t]=ty; bo[tx-1][ty]=1; } if(tx+1<=n&&a[tx+1][ty]=='.'&&!bo[tx+1][ty]){ dis[pp[pa(tx+1,ty)]][now]=(tx==x&&ty==y?1:dis[pp[pa(tx,ty)]][now]+1); xx[++t]=tx+1; yy[t]=ty; bo[tx+1][ty]=1; } if(ty-1>0&&a[tx][ty-1]=='.'&&!bo[tx][ty-1]){ dis[pp[pa(tx,ty-1)]][now]=(tx==x&&ty==y?1:dis[pp[pa(tx,ty)]][now]+1); xx[++t]=tx; yy[t]=ty-1; bo[tx][ty-1]=1; } if(ty+1<=m&&a[tx][ty+1]=='.'&&!bo[tx][ty+1]){ dis[pp[pa(tx,ty+1)]][now]=(tx==x&&ty==y?1:dis[pp[pa(tx,ty)]][now]+1); xx[++t]=tx; yy[t]=ty+1; bo[tx][ty+1]=1; } }}int dep[50005],q[50005];bool bfs(){ memset(dep,0,sizeof dep); dep[S]=1; h=t=1; q[1]=S; while(h<=t){ int x=q[h++]; for(int i=head[x];i;i=ed[i].next){ if(ed[i].f&&!dep[ed[i].v]){ dep[ed[i].v]=dep[x]+1; q[++t]=ed[i].v; if(ed[i].v==T) return 1; } } } return 0;}int dfs(int x,int f){ if(x==T||f==0) return f; int ans=0; for(int i=head[x];i;i=ed[i].next){ if(ed[i].f&&dep[ed[i].v]==dep[x]+1){ int nxt=dfs(ed[i].v,min(f,ed[i].f)); ed[i].f-=nxt; ed[i^1].f+=nxt; ans+=nxt; f-=nxt; if(f==0) break; } } if(ans==0)dep[x]=-1; return ans;}int dinic(){ int ans=0; while(bfs()) ans+=dfs(S,inf); return ans;}bool work(int x){ e=2; memset(head,0,sizeof head); S=per+x*door+1;T=S+1; for(int i=1;i<=per;i++) for(int j=1;j<=door;j++) for(int k=dis[i][j]==0?inf:dis[i][j];k<=x;k++) add(i,per+(k-1)*door+j,1); for(int i=1;i<=per;i++) add(S,i,1); for(int i=per+1;i<=per+x*door;i++) add(i,T,1); if(dinic()==per) return 1; return 0;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=m;j++){ a[i][j]=s[j]; pos[++p]=make_pair(i,j); if(a[i][j]=='.') pp[pos[p]]=++per; if(a[i][j]=='D') dd[pos[p]]=++door; } } for(int i=1;i<=m;i++){ if(a[1][i]=='D')bfs(1,i); if(a[n][i]=='D')bfs(n,i); } for(int i=1;i<=n;i++){ if(a[i][1]=='D')bfs(i,1); if(a[i][m]=='D')bfs(i,m); } for(int i=1;i<=per;i++){ bool booo=1; for(int j=1;j<=door;j++) if(dis[i][j]) {booo=0;break;} if(booo==1){ printf("impossible\n"); return 0; } } int l=1,r=324,mid; while(l+1
转载于:https://www.cnblogs.com/Ren-Ivan/p/7746729.html