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

思路:

首先bfs求出每个空地到每个门的最短距离,注意中间不能经过任何门.好像是原题说过只要经过门就算是退出了.

随后我们二分答案,从原点到每块空地连容量为1的边,从每扇门到汇点连容量为(当前二分的答案)时间的边,对于每块空地和每扇门,若距离不超过时间,则从空地到门连一条容量为1的边.

好像唯一的trick就是从门到汇点的边?不过大家自己YY一下吧.

反正不难.

#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 21
#define M 21
int n,m;
char s[M];
 
int ty[N][M];
 
int d[N][M];
 
static const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct Ins{
    int x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
};
void bfs(int x,int y){
    static queue<Ins>q;
    d[x][y]=0,q.push(Ins(x,y));
    while(!q.empty()){
        Ins tmp=q.front();q.pop();
        for(int k=0;k<4;++k){
            int nx=tmp.x+dx[k],ny=tmp.y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ty[nx][ny]==1&&d[nx][ny]==-1)
                d[nx][ny]=d[tmp.x][tmp.y]+1,q.push(Ins(nx,ny));
        }
    }
}
 
struct MaxflowSolver{
    static const int V=1010,E=200010;
    int head[V],next[E],end[E],flow[E],ind,d[V],inq[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
            if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
        }d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
    }
}Stg;
 
int lab[N][M];
 
int main(){
    scanf("%d%d",&n,&m);register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]=='.')ty[i][j]=1;else if(s[j]=='D')ty[i][j]=2;
    }
     
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j])lab[i][j]=++id;
     
    int L=0,R=1<<30,mid;
    while(L<R){
        mid=(L+R)>>1;
        Stg.reset();
        int cnt=0;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==1)Stg.make(0,lab[i][j],1),++cnt;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2)Stg.make(lab[i][j],n*m+1,mid);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2){
            memset(d,-1,sizeof d),bfs(i,j);
            for(int p=1;p<=n;++p)for(int q=1;q<=m;++q)if(ty[p][q]==1&&d[p][q]!=-1)
                if(d[p][q]<=mid)Stg.make(lab[p][q],lab[i][j],1);
        }
        if(Stg.Maxflow(0,n*m+1)==cnt)R=mid;else L=mid+1;
    }
     
    if(L==1<<30)puts("impossible");else printf("%d",L);
    return 0;
}