AC日记——[HNOI2007]紧急疏散evacuate bzoj 1189

[HNOI2007]紧急疏散evacuate

思路：

　　处理每个人到门的最短路；

　　然后二分答案；

　　s向人连边流量1；

　　人向门拆分后的点连边流量1（拆成400，前一个点连当前点流量INF）；

　　然后门向t连边流量二分的答案；

　　如果最后流量等于人的个数，则true；

来，上代码：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxm 3000001

#define INF 0x7fffffff

const int dx[]={,-,,,};

const int dy[]={,,,,-};

int n,m,d[][],tot,s,t,quex[maxm],quey[maxm],qued[maxm];

int head[],cnt,deep[],E[maxm],V[maxm],F[maxm],size,iap;

char map[][];

bool if_[][];

void bfs(int sx,int sy)

{

    int h=,tail=;

    memset(if_,false,sizeof(if_));

    quex[]=sx,quey[]=sy,qued[]=,if_[sx][sy]=true;

    while(h<tail)

    {

        int nowx=quex[h],nowy=quey[h],nowd=qued[h++];

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

        {

            int x=nowx+dx[i],y=nowy+dy[i],dd=nowd+;

            if(x>&&x<=n&&y>&&y<=m&&map[x][y]=='.'&&!if_[x][y])

            {

                if_[x][y]=true,d[tot][(x-)*m+y]=dd;

                quex[tail]=x,quey[tail]=y,qued[tail++]=dd;

            }

        }

    }

}

inline void edge_add(int u,int v,int f)

{

    E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;

}

bool BFS()

{

    memset(deep,-,sizeof(deep));

    deep[s]=;queue<int>que;que.push(s);

    while(!que.empty())

    {

        int now=que.front();que.pop();

        for(int i=head[now];i;i=E[i])

        {

            if(F[i]>&&deep[V[i]]<)

            {

                deep[V[i]]=deep[now]+;

                if(V[i]==t) return true;

                que.push(V[i]);

            }

        }

    }

    return false;

}

int flowing(int now,int flow)

{

    if(now==t||flow<=) return flow;

    int oldflow=;

    for(int i=head[now];i;i=E[i])

    {

        if(F[i]>&&deep[V[i]]==deep[now]+)

        {

            int pos=flowing(V[i],min(flow,F[i]));

            flow-=pos,oldflow+=pos;

            F[i]-=pos,F[i^]+=pos;

            if(flow==) return oldflow;

        }

    }

    if(oldflow==) deep[now]=-;

    return oldflow;

}

bool check(int k)

{

    memset(head,,sizeof(head));cnt=;

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

    {

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

        {

            if(map[i][j]=='.') edge_add(s,(i-)*m+j,);

        }

    }

    for(int i=;i<=tot;i++)

    {

        int kop=size*i+tot;

        edge_add(size+i,t,k);

        for(int j=;j<=k;j++)

        {

            if(j!=) edge_add(kop+j-,kop+j,INF);

            edge_add(kop+j,size+i,);

        }

        for(int j=;j<=size;j++) if(d[i][j]<=k) edge_add(j,kop+d[i][j],);

    }

    int pos=;

    while(BFS())

    pos+=flowing(s,INF);

    if(pos>=iap) return true;

    else return false;

}

int main()

{

    scanf("%d%d",&n,&m);

    memset(d,/,sizeof(d));

    for(int i=;i<=n;i++) scanf("%s",map[i]+);

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

    {

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

        {

            if(map[i][j]=='D')

            {

                tot++;

                bfs(i,j);

            }

            if(map[i][j]=='.') iap++;

        }

    }

    t=,size=n*m;

    int l=,r=size,ans=-;

    while(l<=r)

    {

        int mid=l+r>>;

        if(check(mid)) ans=mid,r=mid-;

        else l=mid+;

    }

    if(ans==-) cout<<"impossible";

    else cout<<ans;

    return ;

}