1189: [HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2293 Solved: 715
Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
Input
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。
Output
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出'impossible'（不包括引号）。
Sample Input
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
HINT
2015.1.12新加数据一组，鸣谢1756500824
C++语言请用scanf("%s",s)读入！
Source
网络流，二分答案
将门拆点，每个门在每个时间对应一个点，从该点到汇点连一条容量为1的边，代表每单位时间可以出去一个人。
从原点向每个初始有人的点连一条容量为1的边。
二分花费时间，从每个有人的位置到限定时间内该位置能到达的门（预处理出最短距离）连一条容量为1的边，若最大流==人数，那么该时间可行。
↑因为看着数据挺小，用枚举答案代替了二分答案，这样做的好处是每次时间++，可以在原来的残量网络上加边，不需重构图。
↑但写出来还是不如二分快。
↑原来是我自己常数写挂了
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int INF=1e9;
const int mx[]={,,,-,};
const int my[]={,,,,-};
const int mxn=;
struct edge{
int v,nxt,f;
}e[];
int hd[mxn*mxn],mct=;
inline void add_edge(int u,int v,int c){
e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=c;hd[u]=mct;return;
}
inline void insert(int u,int v,int c){
add_edge(u,v,c);add_edge(v,u,);
return;
}
vector<pair<int,int> >pos;
char mp[mxn][mxn];
int dis[mxn][mxn][mxn];
int id[mxn][mxn],ict=;
int n,m,S,T;
int tot=,dr=,ans=;
int d[mxn*mxn];
bool BFS(){
memset(d,,sizeof d);
queue<int>q;
q.push(S);
d[S]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(!d[v] && e[i].f){
d[v]=d[u]+;
q.push(v);
}
}
}
return d[T];
}
int DFS(int u,int lim){
if(u==T)return lim;
int tmp,f=;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(d[v]==d[u]+ && e[i].f){
tmp=DFS(v,min(lim,e[i].f));
e[i].f-=tmp;
e[i^].f+=tmp;
lim-=tmp;
f+=tmp;
if(!lim)return f;
}
}
d[u]=;
return f;
}
int Dinic(){
int res=;
while(BFS())res+=DFS(S,1e9);
return res;
}
int main(){
int i,j;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
scanf("%s",mp[i]+);
S=;T=;ict=;
for(i=;i<=n;i++)
for(j=;j<=m;j++){
if(mp[i][j]=='X')continue;
id[i][j]=++ict;
if(mp[i][j]=='.'){
tot++;
pos.push_back(make_pair(i,j));
insert(S,id[i][j],);
}
}
memset(dis,0x3f,sizeof dis);
for(i=;i<=n;i++)
for(j=;j<=m;j++){
if(mp[i][j]=='D'){
dr++;
queue< pair<int,int> >q;
q.push(make_pair(i,j));
dis[dr][i][j]=;
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int k=;k<=;k++){
int nx=x+mx[k];
int ny=y+my[k];
if(nx< || nx>n || ny< || ny>m)continue;
if(mp[nx][ny]!='.')continue;
if(dis[dr][nx][ny]>dis[dr][x][y]+){
dis[dr][nx][ny]=dis[dr][x][y]+;
q.push(make_pair(nx,ny));
}
}
}
}
}
for(i=;i<=tot*;i++){//枚举时间
if(i>) for(j=;j<=dr;j++){
insert(ict+dr*(i-)+j,ict+dr*(i-)+j,INF);//在门边等待
}
for(j=;j<=dr;j++)
insert(ict+dr*(i-)+j,T,);//可以撤离一个人
for(j=;j<=dr;j++){
for(int k=;k<pos.size();k++){
int x=pos[k].first;
int y=pos[k].second;
if(mp[x][y]=='.' && dis[j][x][y]==i)
insert(id[x][y],ict+dr*(i-)+j,);//移动到门边
}
}
ans+=Dinic();
if(ans==tot){printf("%d\n",i);return ;}
}
printf("impossible\n");
return ;
}