BZOJ 1189 [HNOI2007]紧急疏散evacuate-白红宇

BZOJ 1189 [HNOI2007]紧急疏散evacuate

阅读量：5761 次

发布时间：2019-06-18

本文共 3058 字，大约阅读时间需要 10 分钟。

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

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

【题目分析】

枚举每一个答案t,对于每一个格子，拆成t+1个点，分别代表每一时刻的这个点，然后建边，每次增大t的时候，再加入一层点，然后满流之后就可以得到答案了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
          #include 
         
          //#include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                 using namespace std; #define maxn 1000005#define inf (0x3f3f3f3f) int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;} int n,m,S,T;char s[21];int a[21][21]; // 0 X 1 . 2 Dint hs[21][21][201];int mov[4][2]={ {1,0},{0,1},{-1,0},{0,-1}}; int fr[maxn],h[maxn],to[maxn],fl[maxn],en=0,ne[maxn]; void add(int a,int b,int r){ to[en]=b; fr[en]=a; fl[en]=r; ne[en]=h[a]; h[a]=en++; to[en]=a; fr[en]=b; fl[en]=0; ne[en]=h[b]; h[b]=en++;} int map[maxn]; bool tell(){ memset(map,-1,sizeof map); queue 
                
                  q; while (!q.empty()) q.pop(); q.push(S); map[S]=0; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=h[x];i>=0;i=ne[i]) { if (fl[i]>0&&map[to[i]]==-1) { map[to[i]]=map[x]+1; q.push(to[i]); } } } if (map[T]==-1) return false; return true;} int zeng(int k,int now){ if (k==T) return now; int ret=0; for (int i=h[k];i>=0&&now>ret;i=ne[i]) { if (fl[i]>0&&map[to[i]]==map[k]+1) { int tmp=zeng(to[i],min(fl[i],now-ret)); ret+=tmp; fl[i]-=tmp; fl[i^1]+=tmp; } } if (!ret) map[k]=-1; return ret;} void init(){memset(h,-1,sizeof h);en=0;} int dinic(){ int r=0,t; while (tell()) while (t=zeng(S,inf)) r+=t; return r;} int sum=0,out=0; int main(){ n=read(); m=read(); for (int i=1;i<=n;++i) { scanf("%s",s+1); for (int j=1;j<=m;++j) { if (s[j]=='X') a[i][j]=0; else if (s[j]=='.') a[i][j]=1,sum++; else if (s[j]=='D') a[i][j]=2; } } init();S=0; T=maxn-1; int cnt=0; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) for (int k=0;k<=200;++k) hs[i][j][k]=++cnt; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (a[i][j]==1) add(S,hs[i][j][0],1); for (int t=0;t<130;++t) { for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) { if (a[i][j]==1) { add(hs[i][j][t],hs[i][j][t+1],inf); for (int l=0;l<4;++l) { int tx=i+mov[l][0],ty=j+mov[l][1]; if (tx<1||tx>n||ty<1||ty>m||a[tx][ty]==0) continue; add(hs[i][j][t],hs[tx][ty][t+1],inf); } } else if (a[i][j]==2) { add(hs[i][j][t],T,1); add(hs[i][j][t],hs[i][j][t+1],inf); } } out+=dinic(); if (out==sum) { printf("%d\n",t); return 0; } } printf("impossible\n");}

转载于:https://www.cnblogs.com/SfailSth/p/6193548.html

你可能感兴趣的文章