「LuoguP3191」 [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

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~~

秒客网