[HNOI2007]紧急疏散EVACUATE

题目传送门：[HNOI2007]紧急疏散EVACUATE

bfs+二分+最大流

#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>




const int N=21000,M=1e7;
const int inf=1e9;
char map[41][41];
int n,m,S,T,tim[400][41][41],num[41][41],cnt;
int kk;
int min(int x,int y) 
{
    return x>y?y:x;
}
namespace Dinic
{

    int e[M],ne[M];
    int q[N],cur[N],d[N],h[N],idx;
    int f[M];
    void init()
    {
        memset(h,-1,sizeof h);
        idx=0;
        
    }
    void add(int a,int b,int c)
    {
        e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
        e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
    }
    inline int find(int u,int limit)
    {
        if(u==T)
        {
            return limit;
        }
        int flow=0;
        for(int i=cur[u];~i&&flow<limit;i=ne[i])
        {
            cur[u]=i;
            int ver=e[i];
            if(d[ver]==d[u]+1&&f[i])
            {
                int t=find(ver,min(f[i],limit-flow));
                if(!t) d[ver]=-1;
                f[i]-=t;
                f[i^1]+=t;
                flow+=t;
            }
        }
        return flow;
    }
    inline bool bfs()
    {
        int hh=0,tt=0;
        memset(d,-1,sizeof d);
        q[0]=S,d[S]=0,cur[S]=h[S];
    
        while(hh<=tt)
        {
            int t=q[hh++];
            for(int i=h[t];~i;i=ne[i])
            {
                int ver=e[i];
                if(d[ver]==-1&&f[i])
                {
                    d[ver]=d[t]+1;
                    cur[ver]=h[ver];
                    if(ver==T) return true;
                    q[++tt]=ver;
                }
            }
        }
        return false;
    }
    inline int dinic()
    {
        int ans=0,r;
        while(bfs()) while(r=find(S,inf)) ans+=r;
        return ans;
    }
    
}

namespace BFS
{
	struct node{int x,y;};
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
std::queue<int>Q;
std::queue<node>QQ;
void bfs(int k,int p,int q)//第k扇门，它的位置是(p,q)
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			tim[k][i][j]=inf;
	tim[k][p][q]=0;QQ.push((node){p,q});
	while (!QQ.empty())
	{
		int x=QQ.front().x,y=QQ.front().y;QQ.pop();
		for (int d=0;d<4;d++)
		{
			int i=x+dx[d],j=y+dy[d];
			if (i<1||i>n||j<1||j>m||map[i][j]!='.') continue;//这里如果写成" g[i][j]=='X' "的话在BZOJ上会WA(但是洛谷可以AC)
			if (tim[k][i][j]>tim[k][x][y]+1)
				tim[k][i][j]=tim[k][x][y]+1,QQ.push((node){i,j});
		}
	}
}
    

}

inline bool check(int mid)
{
	Dinic::init();
	S=kk*mid+cnt+1;T=S+1;
	for(int i=1;i<=cnt;i++)
	{
		Dinic::add(S,kk*mid+i,1);
	}
	for(int i=1;i<=kk;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int p=1;p<=m;p++)
			{
				if(tim[i][j][p]<=mid&&map[j][p]=='.')
				{
					Dinic::add(kk*mid+num[j][p],(i-1)*mid+tim[i][j][p],1);
				}
			}
		}
	}
	
	for(int i=1;i<=kk;i++)
	{
		for(int j=1;j<=mid;j++)
		{
			Dinic::add((i-1)*mid+j,T,1);
			if(j<mid) Dinic::add((i-1)*mid+j,(i-1)*mid+j+1,inf);
		}
	}
	
	int ff=Dinic::dinic();
	return ff==cnt;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    	scanf("%s",map[i]+1);
	}
  
    
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		if(map[i][j]=='D') 
    		{
    			BFS::bfs(++kk,i,j);
			}
			else if(map[i][j]=='.')
			{
				num[i][j]=++cnt;
			}
		}
	}
    
    int l=0,r=cnt+1,mid;
    
    while(l<r)
    {
    	mid=(l+r)>>1;
    	if(check(mid)) r=mid;
    	else l=mid+1;
    	
	}
    if(l==cnt+1) printf("impossible\n");
    else printf("%d\n",l);
    
    
    
    return 0;
}