【法一】枚举Time(0~N*M):
S->'.'(1);
'D'->T(Time);
'.'->'D'(dis(用BFS预处理，注意一旦到达'D'，BFS就不能继续扩展了，注意dis的初值0x7f)<=Time ? 1 : 0);
判断是否满流;
#include#include #include #include using namespace std;#define INF 2147483647#define MAXN 411#define MAXM 350001int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM];int d[MAXN],cur[MAXN];queue q;int n,S,T,N,M;void Init_Dinic(){memset(first,-1,sizeof(first)); en=0; S=0; n=N*M+2; T=N*M+1;}void AddEdge(const int &U,const int &V,const int &W){v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++;v[en]=U; next[en]=first[V]; first[V]=en++;}bool bfs(){ memset(d,-1,sizeof(d)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==-1 && cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1;}int dfs(int U,int a){ if(U==T || !a) return a; int Flow=0,f; for(int &i=cur[U];i!=-1;i=next[i]) if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow;}int max_flow(){ int Flow=0,tmp=0; while(bfs()) { memcpy(cur,first,(n+5)*sizeof(int)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow;}int dis[22*22][22*22];bool vis[22][22];char map[22][22];int num[22][22];struct Node{ int x,y,d; Node(const int &a,const int &b,const int &c) {x=a;y=b;d=c;} Node(){}};const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};int man[22*22],door[22*22],summ,sumd;int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;++i) scanf("%s",map[i]+1); for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) { num[i][j]=++en; if(map[i][j]=='.') man[++summ]=en; else if(map[i][j]=='D') door[++sumd]=en; } memset(dis,0x7f,sizeof(dis)); queue q; for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) if(map[i][j]=='.') { memset(vis,0,sizeof(vis)); q.push(Node(i,j,0)); vis[i][j]=1; while(!q.empty()) { Node U=q.front(); q.pop(); for(int k=0;k<4;++k) { int tx=U.x+dx[k],ty=U.y+dy[k]; if(tx>=1 && tx<=N && ty>=1 && ty<=M && map[tx][ty]!='X' && (!vis[tx][ty])) { if(map[tx][ty]=='D') { dis[num[i][j]][num[tx][ty]]=U.d+1; continue;//注意：到了门立刻离开，不能继续。 } vis[tx][ty]=1; q.push(Node(tx,ty,U.d+1)); } } } } for(int Time=0;Time<=N*M;++Time) { Init_Dinic(); for(int i=1;i<=summ;++i) AddEdge(S,man[i],1); for(int i=1;i<=sumd;++i) AddEdge(door[i],T,Time); for(int i=1;i<=summ;++i) for(int j=1;j<=sumd;++j) if(dis[man[i]][door[j]]<=Time) AddEdge(man[i],door[j],1); if(max_flow()==summ) { printf("%d\n",Time); return 0; } } puts("impossible"); return 0;}
【法二】可以二分答案，但是边界总是挂……分块答案。
#include#include #include #include #include using namespace std;#define INF 2147483647#define MAXN 411#define MAXM 350001int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM];int d[MAXN],cur[MAXN];queue q;int n,S,T,N,M;void Init_Dinic(){memset(first,-1,sizeof(first)); en=0; S=0; n=N*M+2; T=N*M+1;}void AddEdge(const int &U,const int &V,const int &W){v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++;v[en]=U; next[en]=first[V]; first[V]=en++;}bool bfs(){ memset(d,-1,sizeof(d)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==-1 && cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1;}int dfs(int U,int a){ if(U==T || !a) return a; int Flow=0,f; for(int &i=cur[U];i!=-1;i=next[i]) if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow;}int max_flow(){ int Flow=0,tmp=0; while(bfs()) { memcpy(cur,first,(n+5)*sizeof(int)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow;}int dis[22*22][22*22];bool vis[22][22];char map[22][22];int num[22][22];struct Node{ int x,y,d; Node(const int &a,const int &b,const int &c) {x=a;y=b;d=c;} Node(){}};const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};int man[22*22],door[22*22],summ,sumd;void Rebuild(const int &Time){ Init_Dinic(); for(int i=1;i<=summ;++i) AddEdge(S,man[i],1); for(int i=1;i<=sumd;++i) AddEdge(door[i],T,Time); for(int i=1;i<=summ;++i) for(int j=1;j<=sumd;++j) if(dis[man[i]][door[j]]<=Time) AddEdge(man[i],door[j],1);}int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;++i) scanf("%s",map[i]+1); for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) { num[i][j]=++en; if(map[i][j]=='.') man[++summ]=en; else if(map[i][j]=='D') door[++sumd]=en; } memset(dis,0x7f,sizeof(dis)); queue q; for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) if(map[i][j]=='.') { memset(vis,0,sizeof(vis)); q.push(Node(i,j,0)); vis[i][j]=1; while(!q.empty()) { Node U=q.front(); q.pop(); for(int k=0;k<4;++k) { int tx=U.x+dx[k],ty=U.y+dy[k]; if(tx>=1 && tx<=N && ty>=1 && ty<=M && map[tx][ty]!='X' && (!vis[tx][ty])) { if(map[tx][ty]=='D') { dis[num[i][j]][num[tx][ty]]=U.d+1; continue;//注意：到了门立刻离开，不能继续。 } vis[tx][ty]=1; q.push(Node(tx,ty,U.d+1)); } } } } int sz=sqrt(N*M),last=0; for(int Time=0;last<=N*M;Time+=sz) { Rebuild(Time); if(max_flow()>=summ) { for(int i=last+1;i<=Time;++i) { Rebuild(i); if(max_flow()==summ) {printf("%d\n",i); return 0;} } return 0; } last=Time; } puts("impossible"); return 0;}