BZOJ1189:[HNOI2007]紧急疏散EVACUATE(最大流,枚举)

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

Solution

$Update$：写假了，先别看了QwQ

这个题……有点像跳舞那个题emmmm……
答案肯定是满足单调性的，所以我们可以枚举
（可以和跳舞那个题一样二分，不过二分就要每次重新添加边，太麻烦）
先判断impossible，BFS判断就行。
建图：超级源点-人-门-超级汇点
枚举秒数，每一秒就在门和超级汇点间连一条容量1的边，意味着当前秒这个门可以多出一个人了
若某个人到某个门耗费的时间为当前秒数，就在人和门间连一条容量为1的边
之后跑一边最大流，若最大流为人数的话就说明人可以全跑出去了
PS每次跑最大流的时候之前的Ans不能清零emmm

Code

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #define MAXM (100000+10)

 #define MAXN (1010+10)

 using namespace std;

 struct node

 {

     int Flow;

     int next;

     int to;

 }edge[MAXM*];

 int Depth[MAXN],Q[MAXN];

 int head[MAXN],num_edge;

 int n,m,s,e=,d,INF;

 int a[MAXN][MAXN];

 int num[MAXN][MAXN];

 int dis[MAXN][MAXN];

 int PEOPLE[MAXN],P_sum;

 int DOOR[MAXN],D_sum;

 int dx[]={,,-,,},dy[]={,,,,-};

 int q[][];

 int Ans;

 bool used[][];

 char ch[];

 void add(int u,int v,int l)

 {

     edge[++num_edge].to=v;

     edge[num_edge].Flow=l;

     edge[num_edge].next=head[u];

     head[u]=num_edge;

 }

 bool Bfs(int s,int e)

 {

     int Head=,Tail=;

     memset(Depth,,sizeof(Depth));

     Depth[s]=;

     Q[]=s;

     while (Head<Tail)

     {

         int x=Q[++Head];

         for (int i=head[x];i!=;i=edge[i].next)

             if (!Depth[edge[i].to] && edge[i].Flow>)

             {

                 Depth[edge[i].to]=Depth[x]+;

                 Q[++Tail]=edge[i].to;

             }

     }

     if (Depth[e]>) return true;

     return false;

 }

 int Dfs(int x,int low)

 {

     int Min,f=;

     if (x==e || low==)

         return low;

     for (int i=head[x];i!=;i=edge[i].next)

         if (edge[i].Flow> && Depth[edge[i].to]==Depth[x]+ && (Min=Dfs(edge[i].to , min(low,edge[i].Flow) )))

         {

             edge[i].Flow-=Min;

             edge[((i-)^)+].Flow+=Min;

             f+=Min;

             low-=Min;

         }

     return f;

 }

 int Dinic(int s,int e)

 {

 //    int Ans=0;

     while (Bfs(s,e))

             Ans+=Dfs(s,0x7fffffff);

     return Ans;

 }

 void DISTANCE(int x,int y)

 {

     int Head=,Tail=;

     memset(used,false,sizeof(used));

     q[][]=x;

     q[][]=y;

     used[x][y]=true;

     while (Head<Tail)

     {

         ++Head;

         for (int i=;i<=;++i)

         {

             int xx=q[Head][]+dx[i];

             int yy=q[Head][]+dy[i];

             if (!used[xx][yy] && a[xx][yy])

             {

                 used[xx][yy]=true;

                 dis[num[x][y]][num[xx][yy]]=dis[num[x][y]][num[q[Head][]][q[Head][]]]+;

                 q[++Tail][]=xx;

                 q[Tail][]=yy;

             }

         }

     }

 }

 int main()

 {

     memset(&INF,0x7f,sizeof(INF));

     int n,m,cnt=;

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;++i)

     {

         scanf("%s",ch);

         for (int j=;j<=m;++j)

         {

             if (ch[j-]=='X')

                 continue;

             num[i][j]=++cnt;

             if (ch[j-]=='.')

             {

                 a[i][j]=;

                 PEOPLE[++P_sum]=num[i][j];

             }

             else

             {

                 a[i][j]=;

                 DOOR[++D_sum]=num[i][j];

             }

         }

     }

     for (int i=;i<=n;++i)

         for (int j=;j<=m;++j)

             if (a[i][j])

                 DISTANCE(i,j);

     for (int i=;i<=P_sum;++i)

     {

         bool flag=false;

         for (int j=;j<=D_sum;++j)

             if (dis[PEOPLE[i]][DOOR[j]]!=)

             {

                 flag=true;

                 break;

             }

         if (!flag)

         {

             printf("impossible\n");

             return ;

         }

     }

     for (int i=;i<=P_sum;++i)

     {

         add(,PEOPLE[i],);

         add(PEOPLE[i],,);

     }

     for (int i=;i<=;++i)

     {

         for (int j=;j<=D_sum;++j)

         {

             add(DOOR[j],,);

             add(,DOOR[j],);

         }

         for (int j=;j<=P_sum;++j)

             for (int k=;k<=D_sum;++k)

                 if (dis[PEOPLE[j]][DOOR[k]]==i)

                 {

                     add(PEOPLE[j],DOOR[k],);

                     add(DOOR[k],PEOPLE[j],);

                 }

         if (Dinic(,)==P_sum)

         {

             printf("%d",i);

             return ;

         }

     }

 }

巴特西