时间戳

首页 > 技术文章 > [HNOI2007]紧急疏散EVACUATE （湖南2007年省选）

[HNOI2007]紧急疏散EVACUATE （湖南2007年省选）

huangdalaofighting 2017-05-07 14:10 原文

[HNOI2007]紧急疏散EVACUATE

题目描述

发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

输入输出格式

输入格式：

 

输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。

 

输出格式：

 

只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出'impossible'（不包括引号）。

 

输入输出样例

输入样例#1：
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
输出样例#1：
3

说明

2015.1.12新加数据一组，鸣谢1756500824

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

题解：

这是一道二分答案与网络流算法的结合的题目，小编也是头一次做这样的题目，所以被坑了很久。

一开始没有什么头绪，后来才发现可以先SPFA一下每一个点到门的距离（也就是时间），然后二分时间求解。

1.这道题可以考虑拆点，也可以考虑拆门，显然拆门更简单，于是就果断将每一个门拆成mid个不同的点，如果一个点可以在mid时间内到达一个门d，那么就将这个点和d的mid分点连在一起。

2.虚拟一个汇点和每一个门连一条流量为1的边，虚拟一个源点和每一个点连一条流量为1的边，其余的边流量为最大值。（这样就保证了同一时间只有一个人可以通过一扇门）

3.然后不断地跑Dinic求最大流。如果可行则说明在mid时间时可以逃生，r=mid-1，如果不可行则l=mid+1。（普通的二分答案）

需要注意的地方：

1.size的初值为奇数，不然就没法跑Dinic。

2.数组的大小。（本人运行错误了好多次，所以代码中的数组开得比较大，实际上不需要这么多）

好了，应该可以上代码了：

 

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
const int inf=233;
int n,m;
int place[201][301],depth[40001],map[40001],dis[1001][1001],root,g,sum,q[501][40001],flow=0;
int xx[40001],yy[40001],t[5]={1,0,-1,0,1};
int head[40001],size;
struct Edge
{
    int next,to,dis;
}edge[100001];
int b[40001];
vector<int>p;
int read()
{
    char i=getchar();int ans=0,f=1;
    while(i<'0'||i>'9')if(i=='-')f=-1,i=getchar();
    while(i>='0'&&i<='9')ans=ans*10+i-'0',i=getchar();
    return ans*f;
}
void spfa(int x,int y)
{
    int i,j,head=0,tail=0;
    xx[tail]=x;yy[tail++]=y;
    for(i=1;i<=g;i++)dis[place[x][y]][i]=inf;
    dis[place[x][y]][place[x][y]]=0;
    while(head!=tail)
    {
        int xxx=xx[head],yyy=yy[head++];
        for(i=0;i<4;i++)
        {
            int nx=xxx+t[i],ny=yyy+t[i+1];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[place[nx][ny]]&&dis[place[x][y]][place[nx][ny]]>dis[place[x][y]][place[xxx][yyy]]+1)
            {
                dis[place[x][y]][place[nx][ny]]=dis[place[x][y]][place[xxx][yyy]]+1;
                if(map[place[nx][ny]]==1)
                {
                    xx[tail]=nx;
                    yy[tail++]=ny;
                }
            }
        }
    }
}
void putin(int from,int to,int dis)
{
    size++;
    edge[size].next=head[from];
    edge[size].to=to;
    edge[size].dis=dis;
    head[from]=size;
}
void in(int from,int to,int dis)
{
    putin(from,to,dis);
    putin(to,from,0);
}
bool bfs()
{
    int i;
    for(i=root;i<=g;i++)depth[i]=0;
    int top=0,tail=0;
    b[tail++]=root;depth[root]=1;
    while(top!=tail)
    {
        int x=b[top++];
        if(x==g)return 1;
        for(i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if(depth[y]==0&&edge[i].dis)
            {
                depth[y]=depth[x]+1;
                b[tail++]=y;
            }
        }
    }
    return 0;
}
int dfs(int root,int mmax)
{
    int i;
    if(root==g)return mmax;
    int rev=0;
    for(i=head[root];i;i=edge[i].next)
    {
        int y=edge[i].to,x=edge[i].dis;
        if(depth[y]==depth[root]+1&&x)
        {
            int mmin=min(mmax-rev,x);
            x=dfs(y,mmin);
            edge[i].dis-=x;
            edge[i^1].dis+=x;
            rev+=x;
            if(rev==mmax)break;
        }
    }
    return rev;
}
bool judge(int mid)
{
    memset(head,0,sizeof(head));
    size=1;
    g=sum;
    int i,j,k;
    for(i=0;i<p.size();i++)
        for(j=0;j<=mid;j++)
            q[p[i]][j]=++g;
    g++;
    for(i=0;i<p.size();i++)
        for(j=0;j<=mid;j++)
        {
            in(q[p[i]][j],g,1);
            if(j!=mid)in(q[p[i]][j],q[p[i]][j+1],inf);
        }
    int ret=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(map[place[i][j]]==1)
            {
                ret++;
                in(root,place[i][j],1);
                for(k=0;k<p.size();k++)
                {
                    if(dis[place[i][j]][p[k]]<=mid)
                    {
                        in(place[i][j],q[p[k]][dis[place[i][j]][p[k]]],1);
                    }
                }
            }
        }
    }
    flow=0;
    while(bfs())
    {
        flow+=dfs(root,2000000000);
    }
    return flow==ret;
}
int main()
{
    int i,j;
    n=read();m=read();
    root=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        place[i][j]=++g;
    sum=g;
    char ch[101];
    for(i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for(j=1;j<=m;j++)
        {
            if(ch[j]=='.')map[place[i][j]]=1;
            if(ch[j]=='D')map[place[i][j]]=2,p.push_back(place[i][j]);
        }
    }
    if(p.size()==0){printf("impossible");return 0;}
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            if(map[place[i][j]]==1)spfa(i,j);
    }
    int l=0,r=inf,ans=inf;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(ans==inf)printf("impossible");
    else printf("%d\n",ans);
    return 0;
}

 

总结：

1.可以用place[i][j]将二维数组中的每一个位置降成一维的，方便求解。

2.输入字符串时用scanf("%S",ch+1);来避免第一位的下标是0的情况。（根据个人习惯）

3.一定要注意数组大小。（不大不小，才是王道）

 

推荐阅读