# Bzoj1189 [hnoi2007]紧急疏散evacuate

Posted by yjjr's blog on December 25, 2017

# 题目

Description

XXXXX

X…D

XX.XX

X..XX

XXDXX Sample Output 3 HINT

2015.1.12新加数据一组，鸣谢1756500824

C++语言请用scanf(“%s”,s)读入！

# 分析

• 从源点向每个空地连一条流量为1的边
• 每个门向汇点连一条流量为T的边
• 每个空地向可以到达的门连一条流量为T的边

# code

4 5 XXDXX XX.XX X…X XXDXX

ans=3

luogu数据较弱，可以AC，话说我要不要去加强下luogu的数据啊，逃）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},maxn=1e3+6,S=0,T=1001;
int n,m,door=1,cnt,ans,tot,na=-1;
int Map[26][26],last[maxn],h[maxn],que[maxn];
int dis[406][26][26];
char ch[26];
struct node{int x,y,s;}d[maxn];
struct edge{int to,next,v;}e[maxn*maxn];
void insert(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}

bool bfs()
{
mem(h,-1);h[S]=0;que[0]=S;
reg(now)
if(h[e[i].to]==-1&&e[i].v){
h[e[i].to]=h[now]+1;
que[tail++]=e[i].to;
}
}
return h[T]!=-1;
}

int dfs(int x,int f){
if(x==T)return f;
int w,used=0;
reg(x)
if(h[e[i].to]==h[x]+1){
w=dfs(e[i].to,min(e[i].v,f-used));
e[i].v-=w,e[i^1].v+=w,used+=w;
if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void build(int x){
mem(last,0);cnt=1;
rep(i,1,n)
rep(j,1,m)if(Map[i][j]==1)insert(S,(i-1)*m+j,1);
rep(i,2,door)insert(n*m+i,T,x);
rep(i,2,door)
rep(j,1,n)
rep(k,1,m)
if(dis[i][j][k]<=x)insert((j-1)*m+k,n*m+i,x);
}
bool judge(int x){
build(x);ans=0;dinic();if(ans==tot)return 1;return 0;
}
void search(int k,int x,int y){
d[0].x=x,d[0].y=y;
rep(i,0,3){
if(nx<1||ny<1||nx>n||ny>m||Map[nx][ny]!=1)continue;
if(dis[k][nx][ny]==inf){
d[tail].x=nx,d[tail++].y=ny;
}
}
}
}
int main()
{
rep(i,1,n){
scanf("%s",ch);
rep(j,1,m){
if(ch[j-1]=='.')Map[i][j]=1,tot++;
else if(ch[j-1]=='D')Map[i][j]=++door;
}
}
rep(i,2,door)
rep(j,1,n)
rep(k,1,m)dis[i][j][k]=inf;
rep(i,1,n)
rep(j,1,m)
if(Map[i][j]>1)search(Map[i][j],i,j);
int l=0,r=406;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid))na=mid,r=mid-1;
else l=mid+1;
}
//cout<<l<<' '<<r<<endl;
if(na==-1)printf("impossible");
else printf("%d\n",na);
return 0;
}