題意:
給定1張網(wǎng)格圖，圖上的點(diǎn)有3種狀態(tài)
‘X’不可走，’.’空地，’D’門
初始之時每一個空地存在1個人，每一個時刻每一個人都可以走向4個方向中的任意1個方向，并且空地可以停留多個人，但是門所在的地方在某個時刻最多有1個人存在，當(dāng)有1個人到達(dá)門后他就成功逃脫了，可以視為他不存在了。
求所有人都成功逃脫的最小時間。
3<=n<=20,3<=m<=20.
解析:
數(shù)據(jù)范圍給的這么小，第1眼還以為是bfs。。
后來發(fā)現(xiàn)門處人沒法堆疊，而空地可以堆疊這個狀態(tài)我不好記錄。
因而斟酌答案是不是存在單調(diào)性。
結(jié)果這個答案竟然真的存在單調(diào)性。
因而我們可以斟酌2分出最小時間，接下來檢驗(yàn)1下就能夠了。
檢驗(yàn)的進(jìn)程不過就是檢驗(yàn)是不是所有人都可以逃脫。
如果對時間T檢驗(yàn)的話，那末也就是說每一個門最多逃跑T個人。
由于數(shù)據(jù)范圍較小，所以我們斟酌可以對每次2分出來的時間，我們暴力檢驗(yàn)每一個人能從哪些門走，建出圖以后跑1個最大流，檢驗(yàn)流量是不是等于人數(shù)便可。
代碼:
#include #include #include #include #include #define N 510 #define INF 0x3f3f3f3f using namespace std; int head[N]; int cnt,n,m,S,T; struct node
{ int from,to,val,next;
}edge[N*N]; void init()
{ memset(head,-1,sizeof(head));
} void edgeadd(int from,int to,int val)
{
edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;
edge[cnt].next=head[from];
head[from]=cnt++;
} char s[31][31]; int door[N]; int top,cntpeo; int dis[31][31][31][31]; bool v[31][31]; int xx[]={0,1,0,-1,0}; int yy[]={0,0,1,0,-1}; struct Point
{ int x,y;
}pt[N]; void getdoor(int x,int y)
{ memset(v,0,sizeof(v)); queueq;
Point fir;
fir.x=x,fir.y=y;
q.push(fir);
dis[x][y][fir.x][fir.y]=0,v[fir.x][fir.y]=1; while(!q.empty())
{
Point u=q.front();
q.pop(); for(int i=1;i<=4;i++)
{ int tmpx=u.x+xx[i],tmpy=u.y+yy[i]; if(tmpx<=0||tmpx>n||tmpy<=0||tmpy>m)continue; if(v[tmpx][tmpy]||s[tmpx][tmpy]==X)continue;
dis[x][y][tmpx][tmpy]=dis[x][y][u.x][u.y]+1;v[tmpx][tmpy]=1; if(s[tmpx][tmpy]==.)
{
Point tmp;
tmp.x=tmpx,tmp.y=tmpy;
q.push(tmp);
}
}
}
} void pre()
{ memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]==.)
getdoor(i,j);
}
}
} void rebuild(int tim)
{
init(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]==.)
edgeadd(S,(i-1)*m+j,1),edgeadd((i-1)*m+j,S,0); else if(s[i][j]==D)
edgeadd((i-1)*m+j,T,tim),edgeadd(T,(i-1)*m+j,0);
}
} for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]==.)
{ for(int k=1;k<=top;k++) { if(dis[i][j][pt[k].x][pt[k].y]<=tim) edgeadd((i-1)*m+j,(pt[k].x-1)*m+pt[k].y,1),edgeadd((pt[k].x-1)*m+pt[k].y,(i-1)*m+j,0);
}
}
}
}
} int dep[N]; int bfs()
{ memset(dep,0,sizeof(dep)); queue<int>q;
q.push(S);
dep[S]=1; while(!q.empty())
{ int u=q.front();
q.pop(); for(int i=head[u];i!=-1;i=edge[i].next)
{ int to=edge[i].to; if(dep[to]||edge[i].val==0)continue;
dep[to]=dep[u]+1;
q.push(to);
}
} return dep[T]?1:0;
} int dfs(int now,int max_vale)
{ int ret=0; if(now==T)return max_vale; for(int i=head[now];i!=-1;i=edge[i].next)
{ int to=edge[i].to; if(dep[to]!=dep[now]+1||edge[i].val==0)continue; int tmp=dfs(to,min(max_vale-ret,edge[i].val));
edge[i].val-=tmp;
edge[i^1].val+=tmp;
ret+=tmp; if(ret==max_vale)return ret;
} return ret;
} int dinic()
{ int ret=0; while(bfs()) while(int t=dfs(S,INF))
ret+=t; return ret;
} bool check(int tim)
{
rebuild(tim); return dinic()==cntpeo?1:0;
} int main()
{ scanf("%d%d",&n,&m);
S=0,T=n*m+1; for(int i=1;i<=n;i++) { scanf("%s",s[i]+1); for(int j=1;j<=m;j++) { if(s[i][j]==D)
pt[++top].x=i,pt[top].y=j; else if(s[i][j]==.)
cntpeo++;
}
}
pre(); if(top==0)
{puts("impossible");return 0;} int l=cntpeo/top,r=cntpeo; int ans=-1; while(l<=r) { int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1;
} if(ans==-1)puts("impossible"); else printf("%d
",ans);
}
