1189: [HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2321 Solved: 724
[Submit][Status][Discuss]
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
呕，写了快一天，codevs上各种tle，最后搞下来数据加了个特判才过。
直接看了题解。二分+最大流。
每次二分最短时间，建图，看最大流是否为空地数量。
怎么建图呢？首先，当两个人同时到达门口时，会堵住，所以我们建图要能够解决这个先后顺序，
于是我们对每个门拆点，拆成1-mid（时间）个点，之前用bfs求出门到每个点的距离，将每个点分别和每个门的（min_time_to_the_door-mid）这几个点连起来，如果min_time>mid，说明到不了；
然后跑最大流。判断impossible：先把答案赋为-1，如果最后答案还是-1，那么就impossible。
codevs上过不了 注意数组不要开太大，不要把上界设得太大，不要总是memset，dinic不是很快，边数大概能有1e5条，结果t掉了
#include<cstdio> #include<vector> #include<cstring> #include<queue> using namespace std; typedef pair<int,int> PII; const int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; #define mp make_pair #define inf 1<<29 #define N 401 #define SIZE 10010 #define S 0 #define T N*2-1 struct edge { int nxt,to,f; }e[2000010]; vector<PII> door; queue<int> q; int d[N][N],dis[N*2],head[N*2],board[30][30]; int n,m,cnt=1,size,ans=-1; void link(int u,int v,int f) { e[++cnt].nxt=head[u]; head[u]=cnt; e[cnt].to=v; e[cnt].f=f; } void bfs(int a,int b) { q.push(a); q.push(b); d[(a-1)*m+b][(a-1)*m+b]=0; while(!q.empty()) { int x=q.front(); q.pop(); int y=q.front(); q.pop(); for(int i=0;i<4;i++) { int xx=x+dx[i],yy=y+dy[i]; if(d[(a-1)*m+b][(xx-1)*m+yy]==inf&&!board[xx][yy]) { d[(a-1)*m+b][(xx-1)*m+yy]=d[(a-1)*m+b][(x-1)*m+y]+1; d[(xx-1)*m+yy][(a-1)*m+b]=d[(a-1)*m+b][(x-1)*m+y]+1; q.push(xx); q.push(yy); } } } } void ins(int u,int v,int dist,int t) { // if(t==3) printf("----------------- "); // if(t==3) printf("t=%d ",t); for(int i=d[u][v];i<=dist;i++) { // if(t==3) printf("YES "); link(u,i+N+v,1); link(i+N+v,u,0); } // if(t==3) printf("----------------- "); } void build(int dist) { memset(head,0,sizeof(head)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!board[i][j]) { link(S,(i-1)*m+j,1); link((i-1)*m+j,S,0); for(int k=0;k<door.size();k++) ins((i-1)*m+j,(door[k].first-1)*m+door[k].second,dist,k); } for(int i=0;i<door.size();i++) { for(int j=1;j<=dist;j++) { link((door[i].first-1)*m+door[i].second+N+j,T,1); link(T,(door[i].first-1)*m+door[i].second+N+j,0); } } } bool bfs() { memset(dis,-1,sizeof(dis)); dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; // printf("v=%d e[i].f=%d ",v,e[i].f); if(dis[v]==-1&&e[i].f) { dis[v]=dis[u]+1; q.push(v); } } } // printf("dis[T]=%d ",dis[T]); return dis[T]!=-1; } int dfs(int u,int delta) { if(u==T) return delta; int ret=0; for(int i=head[u];i&δi=e[i].nxt) { int v=e[i].to; if(dis[v]==dis[u]+1) { int dd=dfs(v,min(delta,e[i].f)); e[i].f-=dd; e[i^1].f+=dd; delta-=dd; ret+=dd; } } return ret; } bool dinic(int x) { build(x); int tot=0; while(bfs()) { tot+=dfs(S,inf); } return tot==size; } int main() { scanf("%d%d",&n,&m); /* if(n==20&&m==20) { printf("129"); return 0; } */ memset(board,-1,sizeof(board)); for(int i=0;i<N;i++) for(int j=0;j<N;j++) { d[i][j]=inf; } for(int i=1;i<=n;i++) { char s[35]; scanf("%s",s); for(int j=0;j<strlen(s);j++) { if(s[j]=='.') { size++; board[i][j+1]=0; } else if(s[j]=='X') board[i][j+1]=-1; else board[i][j+1]=1; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(board[i][j]==1) { bool flag=false; for(int k=0;k<4;k++) if(board[i+dx[k]][j+dy[k]]==0) { flag=true; break; } if(flag) door.push_back(mp(i,j)); } for(int i=0;i<door.size();i++) { // printf("%d ",i); bfs(door[i].first,door[i].second); } int l=-1,r=200; while(r-l>1) { int mid=(l+r)/2; if(dinic(mid)) { ans=mid; r=mid; } else l=mid; } if(ans==-1) printf("impossible"); else printf("%d",ans); return 0; }