首页 > 代码库 > Bzoj1189 [HNOI2007]紧急疏散evacuate

Bzoj1189 [HNOI2007]紧急疏散evacuate

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

5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

Sample Output

3

HINT

 

2015.1.12新加数据一组,鸣谢1756500824


C++语言请用scanf("%s",s)读入!

 

Source

 

网络流,二分答案

将门拆点,每个门在每个时间对应一个点,从该点到汇点连一条容量为1的边,代表每单位时间可以出去一个人。

从原点向每个初始有人的点连一条容量为1的边。

二分花费时间,从每个有人的位置到限定时间内该位置能到达的门(预处理出最短距离)连一条容量为1的边,若最大流==人数,那么该时间可行。

 

↑因为看着数据挺小,用枚举答案代替了二分答案,这样做的好处是每次时间++,可以在原来的残量网络上加边,不需重构图。

  ↑但写出来还是不如二分快。

 

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 using namespace std; 10 const int INF=1e9; 11 const int mx[5]={0,1,0,-1,0}; 12 const int my[5]={0,0,1,0,-1}; 13 const int mxn=45; 14 struct edge{ 15     int v,nxt,f; 16 }e[500010]; 17 int hd[mxn*mxn],mct=1; 18 inline void add_edge(int u,int v,int c){ 19     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=c;hd[u]=mct;return; 20 } 21 inline void insert(int u,int v,int c){ 22     add_edge(u,v,c);add_edge(v,u,0); 23     return; 24 } 25 vector<pair<int,int> >pos; 26 char mp[mxn][mxn]; 27 int dis[mxn][mxn][mxn]; 28 int id[mxn][mxn],ict=0; 29 int n,m,S,T; 30 int tot=0,dr=0,ans=0; 31 int d[mxn*mxn]; 32 bool BFS(){ 33     memset(d,0,sizeof d); 34     queue<int>q; 35     q.push(S); 36     d[S]=1; 37     while(!q.empty()){ 38         int u=q.front();q.pop(); 39         for(int i=hd[u];i;i=e[i].nxt){ 40             int v=e[i].v; 41             if(!d[v] && e[i].f){ 42                 d[v]=d[u]+1; 43                 q.push(v); 44             } 45         } 46     } 47     return d[T]; 48 } 49 int DFS(int u,int lim){ 50     if(u==T)return lim; 51     int tmp,f=0; 52     for(int i=hd[u];i;i=e[i].nxt){ 53         int v=e[i].v; 54         if(d[v]==d[u]+1 && e[i].f){ 55             tmp=DFS(v,min(lim,e[i].f)); 56             e[i].f-=tmp; 57             e[i^1].f+=tmp; 58             lim-=tmp; 59             f+=tmp; 60             if(!lim)return f; 61         } 62     } 63     d[u]=0; 64     return f; 65 } 66 int Dinic(){ 67     int res=0; 68     while(BFS())res+=DFS(S,1e9); 69     return res; 70 } 71 int main(){ 72     int i,j; 73     scanf("%d%d",&n,&m); 74     for(i=1;i<=n;i++) 75         scanf("%s",mp[i]+1); 76     S=0;T=1;ict=1; 77     for(i=1;i<=n;i++) 78      for(j=1;j<=m;j++){ 79          if(mp[i][j]==X)continue; 80          id[i][j]=++ict; 81          if(mp[i][j]==.){ 82              tot++; 83              pos.push_back(make_pair(i,j)); 84              insert(S,id[i][j],1); 85         } 86     } 87     memset(dis,0x3f,sizeof dis); 88     for(i=1;i<=n;i++) 89         for(j=1;j<=m;j++){ 90             if(mp[i][j]==D){ 91                 dr++; 92                 queue< pair<int,int> >q; 93                 q.push(make_pair(i,j)); 94                 dis[dr][i][j]=0; 95                 while(!q.empty()){ 96                     int x=q.front().first; 97                     int y=q.front().second; 98                     q.pop(); 99                     for(int k=1;k<=4;k++){100                         int nx=x+mx[k];101                         int ny=y+my[k];102                         if(nx<1 || nx>n || ny<1 || ny>m)continue;103                         if(mp[nx][ny]!=.)continue;104                         if(dis[dr][nx][ny]>dis[dr][x][y]+1){105                             dis[dr][nx][ny]=dis[dr][x][y]+1;106                             q.push(make_pair(nx,ny));107                         }108                     }109                 }110             }111         }112     for(i=1;i<=tot*2;i++){//枚举时间 113         if(i>1)    for(j=1;j<=dr;j++){114             insert(ict+dr*(i-2)+j,ict+dr*(i-1)+j,INF);//在门边等待 115         }116         for(j=1;j<=dr;j++)117             insert(ict+dr*(i-1)+j,T,1);//可以撤离一个人 118         for(j=1;j<=dr;j++){119             for(int k=0;k<pos.size();k++){120                 int x=pos[k].first;121                 int y=pos[k].second;122                 if(mp[x][y]==. && dis[j][x][y]==i)123                     insert(id[x][y],ict+dr*(i-1)+j,1);//移动到门边 124             }125         }126         ans+=Dinic();127         if(ans==tot){printf("%d\n",i);return 0;}128     }129     printf("impossible\n");130     return 0;131 }

 

Bzoj1189 [HNOI2007]紧急疏散evacuate