BZOJ1189: [HNOI2007]紧急疏散evacuate 二分+最大流

1189: [HNOI2007]紧急疏散evacuate

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1132  Solved: 412
[Submit][Status][Discuss]

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

3

 

 

题解：S-'.'-'D'-T;先从门bfs出每个‘.’点到门的距离，注意要每种情况都要计算所以开一个距离数组400*20*20+1，再二分时间为最后‘D’到T的容量；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std ;
typedef long long ll;
inline ll read()
{
    ll x=,f=;char ch=getchar();
    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
    return x*f;
}
//******************************************************************
namespace NetFlow
{
    const int MAXN=,MAXM=,inf=1e9;
    struct Edge
    {
        int v,c,f,nx;
        Edge() {}
        Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
    } E[MAXM];
    int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
    void init(int _n)
    {
        N=_n,sz=; memset(G,-,sizeof(G[])*N);
    }
    void link(int u,int v,int c)
    {
        E[sz]=Edge(v,c,,G[u]); G[u]=sz++;
        E[sz]=Edge(u,,,G[v]); G[v]=sz++;
    }
    int ISAP(int S,int T)
    {//S -> T
        int maxflow=,aug=inf,flag=false,u,v;
        for (int i=;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=;
        for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
        {
            for (int &it=cur[u];~it;it=E[it].nx)
            {
                if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+)
                {
                    if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
                    pre[v]=u,u=v; flag=true;
                    if (u==T)
                    {
                        for (maxflow+=aug;u!=S;)
                        {
                            E[cur[u=pre[u]]].f+=aug;
                            E[cur[u]^].f-=aug;
                        }
                        aug=inf;
                    }
                    break;
                }
            }
            if (flag) continue;
            int mx=N;
            for (int it=G[u];~it;it=E[it].nx)
            {
                if (E[it].c>E[it].f&&dis[E[it].v]<mx)
                {
                    mx=dis[E[it].v]; cur[u]=it;
                }
            }
            if ((--gap[dis[u]])==) break;
            ++gap[dis[u]=mx+]; u=pre[u];
        }
        return maxflow;
    }
    bool bfs(int S,int T)
    {
        static int Q[MAXN]; memset(dis,-,sizeof(dis[])*N);
        dis[S]=; Q[]=S;
        for (int h=,t=,u,v,it;h<t;++h)
        {
            for (u=Q[h],it=G[u];~it;it=E[it].nx)
            {
                if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
                {
                    dis[v]=dis[u]+; Q[t++]=v;
                }
            }
        }
        return dis[T]!=-;
    }
    int dfs(int u,int T,int low)
    {
        if (u==T) return low;
        int ret=,tmp,v;
        for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
        {
            if (dis[v=E[it].v]==dis[u]+&&E[it].c>E[it].f)
            {
                if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
                {
                    ret+=tmp; E[it].f+=tmp; E[it^].f-=tmp;
                }
            }
        }
        if (!ret) dis[u]=-; return ret;
    }
    int dinic(int S,int T)
    {
        int maxflow=,tmp;
        while (bfs(S,T))
        {
            memcpy(cur,G,sizeof(G[])*N);
            while (tmp=dfs(S,T,inf)) maxflow+=tmp;
        }
        return maxflow;
    }
}
struct sss
{
    int x,y,t;
}hh[][];
int n,m;
int ss[][]={-,,,-,,,,};
int tim[][][];
char mp[][];
int tot;
int cnt=;
int xxx[],yyy[];
void bfss(int a,int b,int index)
{
    sss k,kk;
    queue<sss>q;
    k.x=a;
    k.y=b;
    k.t=;
    q.push(k);
    while(!q.empty())
    {
        kk=q.front();
        q.pop();
        for(int i=;i<;i++)
        {
            int xx=kk.x+ss[i][];
            int yy=kk.y+ss[i][];
            if(xx<=||xx>n||yy<=||yy>m)continue;
            if(mp[xx][yy]=='X'||mp[xx][yy]=='D')continue;
            if(kk.t+<tim[index][xx][yy]){
                tim[index][xx][yy]=kk.t+;
                hh[xx][yy].x=a;
                hh[xx][yy].y=b;
                sss kkk;
                kkk.x=xx;
                kkk.y=yy;
                kkk.t=tim[index][xx][yy];

               // cout<<"feinds "<<tim[xx][yy]<<endl;return;
                q.push(kkk);
            }
        }
    }
}
using namespace NetFlow;
int juge(int r)
{
    init();
    for(int i=;i<=n;i++){
        for(int j=;j<=m;j++)
        {
            if(mp[i][j]=='.')
                link(,(i-)*m+j,);
        }
    }
    for(int i=;i<=cnt;i++)link(n*m+i,,r);
    for(int i=;i<=cnt;i++)
    {
        for(int j=;j<=n;j++){
            for(int k=;k<=m;k++)
            {
                if(tim[n*m+i][j][k]<=r)link((j-)*m+k,n*m+i,);
            }
        }
    }
   // cout<<14<<endl;
    if(dinic(,)==tot)return ;
    else return ;
}
int main()
{

    scanf("%d%d",&n,&m);
    tot=;
    for(int i=;i<=n;i++)
    {
        scanf("%s",mp[i]+);
        for(int j=;j<=m;j++)
        {
            if(mp[i][j]=='D')
            {
                cnt++;
                xxx[cnt]=i;
                yyy[cnt]=j;
            }
            if(mp[i][j]=='.')tot++;
        }
    }
   // cout<<"das "<<tot<<endl;
    memset(tim,,sizeof(tim));
   // if(cnt==0){cout<<"impossible"<<endl;return 0;}
    for(int i=;i<=cnt;i++)
    {
        bfss(xxx[i],yyy[i],n*m+i);
    }
    int l=;
    int r=;
    int ans=-;
    while(l<r)
    {
        int mid=(l+r)>>;
        if(juge(mid))
        {
            ans=mid;
            r=mid;
        }
        else l=mid+;
    }
    if(ans==-)cout<<"impossible"<<endl;
    else
    cout<<ans<<endl;
    return ;
}

代码

例子：

4 5
XXDXX
XX.XX
X...X
XXDXX

答案应该输出3

上面的做法是错的，必须要对门的每个时间点都连一条容量为limit-k+1的边才行，

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 5e4+, M = 1e3+, mod = 1e9+, inf = 2e9;

int n,m,vis[][],step[][],all;
char mp[][];

vector< pair<int,int > > D;
vector< pair<int,int > > out[N];
int ss[][] = {-,,,-,,,,};

int h[N],head[N],t = ,S,T,q[N],ans;
struct edge{int to,next,v;}e[];
void adds(int u,int v,int w) {e[t].next=head[u];e[t].v=w;e[t].to=v;head[u]=t++;}
void add(int u,int v,int w) {adds(u,v,w);adds(v,u,);}

int bfs() {
    memset(h,-,sizeof(h));
    int l = ,r = , now;
    q[l] = S;
    h[S] = ;
    while(l != r) {
        now=q[l++];//if(l == 910)l = 0;
        for(int i=head[now];i!=-;i=e[i].next) {
            if(e[i].v&&h[e[i].to] == -) {
                h[e[i].to] = h[now] + ;
                q[r++] = e[i].to;
                //if(r == 910) r = 0;
            }
        }
    }
    if(h[T] == -) return ;
    return ;
}
int dfs(int x,int f) {
    if(x == T) return f;
    int used=,w;
    for(int i=head[x];i!=-;i=e[i].next) {
        if(e[i].v&&h[e[i].to] == h[x]+) {
            w=dfs(e[i].to,min(f-used,e[i].v));
            used+=w;e[i].v-=w;e[i^].v+=w;
            if(used == f) return f;
        }
    }
    return used;
}
int dinic() {
   while(bfs()) {ans+=dfs(S,inf);}
   return ans;
}

int check(int x) {
     S = n*m+,T = S + ;
     t = , memset(head,-,sizeof(head));
     int tot = ;
     for(int i = ; i <= n; ++i) {
        for(int j = ; j <= m; ++j) {
            if(mp[i][j] == '.') {
                add(S,(i-)*m+j,);
                for(int k = ; k < out[(i-)*m+j].size(); ++k) {
                    if(out[(i-)*m+j][k].first <= x)
                        add((i-)*m+j,T+(out[(i-)*m+j][k].second-)*x+out[(i-)*m+j][k].first,);
                }
            }
            if(mp[i][j] == 'D')  {
                add((i-)*m+j,T,x);
                for(int k = ; k <= x; ++k) add(T+(tot-)*x+k,(i-)*m+j,x-k+);
                tot++;
            }
        }
     }
     ans = ;
     if(dinic() == all) return ;
     else return ;
}

void bfs(int x,int y,int who) {
    queue< pair<int ,int > >  q;
    q.push(MP(x,y));
    vis[x][y] = ;
    step[x][y] = ;
    while(!q.empty()) {
        pair<int,int > k = q.front();
        q.pop();
        for(int i =  ; i < ; ++i) {
            int xx = k.first + ss[i][];
            int yy = k.second + ss[i][];

            if(xx <=  || yy <=  || xx > n || yy > m || mp[xx][yy] != '.') continue;
            if(vis[xx][yy]) continue;

            vis[xx][yy] = ;

            q.push(MP(xx,yy));
            step[xx][yy] = step[k.first][k.second]+;
            out[(xx-)*m+yy].push_back(MP(step[xx][yy],who));
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = ; i <= n; ++i) {
        scanf("%s",mp[i]+);
        for(int j = ; j <= m; ++j) {
            if(mp[i][j] == 'D') D.push_back(MP(i,j));
            if(mp[i][j] == '.') all++;
        }
    }

    for(int i = ; i < D.size(); ++i) {
        memset(vis,,sizeof(vis));
        memset(step,,sizeof(step));
        bfs(D[i].first,D[i].second,i+);
    }
    int l = , r = , ans1 = -;
    while(l <= r) {
        int md = (l+r)>>;
        if(check(md)) ans1 = md, r = md - ;
        else l = md + ;
    }
    if(ans1 == -) printf("impossible");
    else printf("%d",ans1);
    return ;
}

修改