「LuoguP3191」 [HNOI2007]紧急疏散EVACUATE（最大流

2022-05-08 12:18:59

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)读入！

题解

首先这只是90分代码并且已经手推出数据被卡也许是代码问题也许是思路问题(遍历题解并没有同样的思路~~但是我真的调了好几个小时了要吐了~~

首先读题很容易想到二分答案

拆点，设空地< i.a >,< i.b > 门< d.a >,< d.b >，设二分的答案为k

从S到每个< i.a >连边为1

每个< i.a >向< i.b >连k，每个< d.a >向< d.b >连k

然后从每个门开始dfs dfs的第一个空地< i.b >向< d.a >连k，之后按dfs序后扫到的空地的< i2.b >向前一个的< i1.a >连k

最后每一个< d.b >向T连k

注意网络流的二分答案一般都要复原操作(把反边流量加到正边上清空反边流量)

~~这道题真的恶心到呕吐有朝一日过了我给你黑~~

~~丑到我都不想看的~~代码~~真的丑到哭泣~~

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int INF=99999999;

char tu[27][27];

int n,m;

int flag=0;

void scan()

{

    cin>>n>>m;

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

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

    cin>>tu[i][j];

    return;

}

int s,t;

int num[27][27];

int ss;

bool sf[27][27];

int mx[5]={0,1,0,-1,0};

int my[5]={0,0,1,0,-1};

struct emm{

    int e,f,v;

}a[1000007];

int h[807];

int tot=1;

void con(int x,int y,int l)

{

    a[++tot].f=h[x];

    h[x]=tot;

    a[tot].e=y;

    a[tot].v=l;

    a[++tot].f=h[y];

    h[y]=tot;

    a[tot].e=x;

    a[tot].v=0;

    return;

}

/*

void dfss(int x,int y)

{

    sf[x][y]=1;

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

    {

        x+=mx[i],y+=my[i];

        if((tu[x][y]=='.'||tu[x][y]=='D')&&!sf[x][y])

        {

            con(num[x][y],ss,1);

            //dfss(x,y);

        }

        x-=mx[i],y-=my[i];

    }

    return;

}

*/

int tag,peo=0;

void dfsss(int bx,int by,int x,int y,int k)

{

    con(num[x][y]+m*n,num[bx][by],k);

    int bbx=x,bby=y;

    sf[x][y]=1;

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

    {

        x+=mx[i],y+=my[i];

        if(tu[x][y]=='.'&&!sf[x][y])dfsss(bbx,bby,x,y,k);

        x-=mx[i],y-=my[i];

    }

    return;

}

void build()

{

    s=0,t=2*m*n+1;

    int tim=0;

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

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

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

    num[0][0]=t;

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

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

    if(tu[i][j]=='.'){

        con(s,num[i][j],1);

        peo++;

    }

    /*

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

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

    if(tu[i][j]=='D'||tu[i][j]=='.'){

        memset(sf,0,sizeof(sf));

        ss=num[i][j];

        dfss(i,j);

    }

    */

    tag=tot;

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

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

    if(tu[i][j]=='.'||tu[i][j]=='D')con(num[i][j],num[i][j]+m*n,-1);

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

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

    if(tu[i][j]=='D'){

    memset(sf,0,sizeof(sf));

    dfsss(0,0,i,j,-1);

    }

    return;

}

void conn(int x,int y,int k)

{

    //cout<<x<<" "<<y<<endl;

    a[++tot].v=k;

    a[++tot].v=0;

    return;

}

void dfss(int bx,int by,int x,int y,int k)

{

    conn(num[x][y]+m*n,num[bx][by],k);

    int bbx=x,bby=y;

    sf[x][y]=1;

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

    {

        x+=mx[i],y+=my[i];

        if(tu[x][y]=='.'&&!sf[x][y])dfss(bbx,bby,x,y,k);

        x-=mx[i],y-=my[i];

    }

    return;

}

void adbuild(int k)

{

    //cout<<"adbuild"<<k<<endl;

    //cout<<"a"<<endl;

    tot=tag;

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

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

    if(tu[i][j]=='.'||tu[i][j]=='D')conn(num[i][j],num[i][j]+m*n,k);

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

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

    if(tu[i][j]=='D'){

    memset(sf,0,sizeof(sf));

    dfss(0,0,i,j,k);

    }

    return;

}

queue<int>q;

int d[807];

inline bool bfs()

{

    memset(d,0,sizeof(d));

    d[s]=1;

    q.push(s);

    while(!q.empty())

    {

        int x=q.front();q.pop();

        for(int i=h[x];i;i=a[i].f)

        if(!d[a[i].e]&&a[i].v)

        {

            d[a[i].e]=d[x]+1;

            q.push(a[i].e);

        }

    }

    return d[t];

}

int dfs(int x,int al)

{

    if(x==t||!al)return al;

    int fl=0;

    for(int i=h[x];i;i=a[i].f)

    if(d[a[i].e]==d[x]+1&&a[i].v)

    {

        if(flag)cout<<x<<" "<<a[i].e<<endl;

        int f=dfs(a[i].e,min(a[i].v,al));

        if(f)

        {

            fl+=f;

            al-=f;

            a[i].v-=f;

            a[i^1].v+=f;

            if(!al)break;

        }

    }

    if(!fl)d[x]=-1;

    return fl;

}

void erfen(int l,int r)

{

    //cout<<"l="<<l<<" r="<<r<<endl;

    if(l==r){if(r==peo+1)cout<<"impossible"<<endl;else cout<<l<<endl;return;}

    int mid=(l+r)/2;

    if(mid==6)flag=1;else flag=0;

    for(int i=2;i<=tag;i+=2){a[i].v+=a[i^1].v;a[i^1].v=0;}

    adbuild(mid);

    int ans=0;

    while(bfs()){ans+=dfs(s,INF);if(flag)cout<<ans<<endl;}

    //cout<<"mid="<<mid<<" ans="<<ans<<endl;

    if(ans==peo)erfen(l,mid);

    else erfen(mid+1,r);

    return;

}

int main()

{

    //freopen("a.in","r",stdin);

    scan();

    build();

    erfen(0,peo+1);

    return 0;

}

出锅数据：

4 4

...D

.XX.

....

XD.X

手推ans=6 程序输出7

~~再也不想调了~~

如果有dalao能看穿的话就救救孩子

深鞠躬~~QAQ~~

码农公寓