1189: [HNOI2007]紧急疏散evacuate

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3831 Solved: 1119
[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

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

Sample Output

HINT

2015.1.12新加数据一组，鸣谢1756500824

这题网络流真恶心。。。

二分+最大流

由源点S连向每个空地，容量为1

二分时间time，将每个门拆成time个点，从门bfs到空地（人），如果从空地到门能在x的时间内到达，则将空地连向第x扇门

每扇门连向汇点，容量为1，表示单位时间内只能出去一个人

然后每扇门向下一扇门连线，容量为INF，表示多出来的人等下一扇门

PS：网上大多数题解有错误

4 5
XXXDX
XXX.X
X.X.D
.....

ans=6

大部分题解没有考虑门在单位时间内只能出一人

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 
  7 #define ID(i,j) (i*m+j)
  8 const int INF=0x7f7f7f7f;
  9 const int MAXN=1000000;
 10 const int xx[4]={-1,1,0,0};
 11 const int yy[4]={0,0,-1,1};
 12 
 13 struct Edge
 14 {
 15     int to,w,next;
 16 }E[MAXN];
 17 int node=1,head[MAXN],dis[MAXN];
 18 int s=0,t=1e5+1;
 19 int n,m,ans,sum;
 20 
 21 int mp[40][40];
 22 
 23 void insert(int u,int v,int w)
 24 {
 25     E[++node]=(Edge){v,w,head[u]};
 26     head[u]=node;
 27     E[++node]=(Edge){u,0,head[v]};
 28     head[v]=node;
 29 }
 30 
 31 bool bfs()
 32 {
 33     memset(dis,-1,sizeof(dis));
 34     queue<int> Q;
 35     Q.push(s);
 36     dis[s]=0;
 37     while(!Q.empty())
 38     {
 39         int q=Q.front();Q.pop();
 40         for(int i=head[q];i;i=E[i].next)
 41             if(E[i].w&&dis[E[i].to]==-1)
 42             {
 43                 Q.push(E[i].to);
 44                 dis[E[i].to]=dis[q]+1;
 45             }
 46     }
 47     return dis[t]!=-1;
 48 }
 49 
 50 int dfs(int x,int flow)
 51 {
 52     if(x==t) return flow;
 53     int w,used=0;
 54     for(int i=head[x];i;i=E[i].next)
 55         if(E[i].w&&dis[E[i].to]==dis[x]+1)
 56         {
 57             w=flow-used;
 58             w=dfs(E[i].to,min(w,E[i].w));
 59             E[i].w-=w;
 60             E[i^1].w+=w;
 61             used+=w;
 62             if(used==flow)return flow;
 63         }
 64     if(!used) dis[x]=-1;
 65     return used;
 66 }
 67 
 68 void dinic()
 69 {
 70     while(bfs()) ans+=dfs(s,INF);
 71 }
 72 
 73 struct NODE
 74 {
 75     int x,y,t;
 76 };
 77 int cnt=0;
 78 
 79 void bfs(NODE N,int time)
 80 {
 81     bool vis[25][25];
 82     queue<NODE> Q;
 83     memset(vis,0,sizeof(vis));
 84     for(int i=0;i<4;i++)
 85     {
 86         int x=N.x+xx[i],y=N.y+yy[i];
 87         if(!vis[x][y])
 88         {
 89             Q.push((NODE){x,y,1});
 90             vis[x][y]=1;
 91         }
 92     }
 93     while(!Q.empty())
 94     {
 95         NODE T=Q.front();Q.pop();
 96         if(T.x<1||T.x>n||T.y<1||T.y>m) continue;
 97         if(T.t>time) continue;
 98         if(mp[T.x][T.y]!=0) continue;
 99         for(int i=0;i<4;i++)
100         {
101             int x=T.x+xx[i],y=T.y+yy[i];
102             if(!vis[x][y])
103             {
104                 Q.push((NODE){x,y,T.t+1});
105                 vis[x][y]=1;
106             }
107         }
108         insert(ID(T.x,T.y),cnt*10000+T.t,1);
109     }
110 }
111 
112 bool check(int x)
113 {
114     cnt=0;
115     node=1;ans=0;
116     memset(head,0,sizeof(head));
117     for(int i=1;i<=n;i++)
118         for(int j=1;j<=m;j++)
119             if(mp[i][j]==0) insert(s,ID(i,j),1);
120             else if(mp[i][j]==-1)
121             {
122                 cnt++;
123                 insert(cnt*10000+1,t,1);
124                 for(int k=2;k<=x;k++)
125                 {
126                     insert(cnt*10000+k,t,1);
127                     insert(cnt*10000+k-1,cnt*10000+k,INF);
128                 }
129                 bfs((NODE){i,j,0},x);
130             }
131     dinic();
132     if(ans==sum) return true;
133     return false;
134 }
135 
136 int main()
137 {
138     char ch[100];
139     scanf("%d%d",&n,&m);
140     for(int i=1;i<=n;i++)
141     {
142         scanf("%s",ch+1);
143         for(int j=1;j<=m;j++)
144             if(ch[j]=='.') sum++;
145             else if(ch[j]=='X') mp[i][j]=1;
146             else if(ch[j]=='D') mp[i][j]=-1;
147     }
148     int left=1,right=n*m;
149     while(left<right)
150     {
151         int mid=(left+right)>>1;
152         if(check(mid)) right=mid;
153         else left=mid+1;
154     }
155     if(right==n*m) printf("impossible");
156     else printf("%d",right);
157     return 0;
158 }