Bzoj1189 [hnoi2007]紧急疏散evacuate

Posted by yjjr's blog on December 25, 2017

标签:网络流,dinic,二分,最大流

题目

题目传送门

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 HINT

2015.1.12新加数据一组,鸣谢1756500824

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

分析

首先每个门做一次bfs,求这扇门到每一个人的时间,然后二分时间T,跑最大流dinic算法,如果流量=人数那么T就是一个可行的答案

具体的建图操作如下:

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

code

本代码目前无法在BZOJ上AC,wxh大爷太毒瘤了,加强的一组数据强悍

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;
inline ll read()
{
	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()
{
	int head=0,tail=1,now;
	mem(h,-1);h[S]=0;que[0]=S;
	while(head<tail){
		now=que[head++];
		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){
	int head=0,tail=1,nx,ny;
	d[0].x=x,d[0].y=y;
	while(head<tail){
		rep(i,0,3){
			nx=d[head].x+dx[i],ny=d[head].y+dy[i];
			if(nx<1||ny<1||nx>n||ny>m||Map[nx][ny]!=1)continue;
			if(dis[k][nx][ny]==inf){
				dis[k][nx][ny]=d[tail].s=d[head].s+1;
				d[tail].x=nx,d[tail++].y=ny;
			}
		}
		head++;
	}
}
int main()
{
	n=read(),m=read();
	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;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr