「BZOJ1189」[HNOI2007] 紧急疏散evacuate

2014年3月7日7,4346

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

题解

对于每个门进行一次bfs，得出每个点到每个门的时间

然后二分时间，每次建图dinic

S到空地连一条容量1的边，每个空地到可到达的门连一条容量1的边，每个门到T连一条容量为时间的边

#include<iostream>
#include<cstdio>
#include<cstring>
#define S 0
#define T 1000
#define inf 0x7fffffff
using namespace std;
int n,m,door=1,cnt,ans,tot,mn=-1;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int mp[21][21],head[1001],h[1001],q[1001];
int dis[401][21][21];
struct data{int x,y,s;}d[401];
struct data2{int to,next,v;}e[1000001];
bool bfs()
{
	int t=0,w=1,i,now;
	memset(h,-1,sizeof(h));
	h[S]=0;q[0]=S;
	while(t<w)
	{
		now=q[t];t++;
		i=head[now];
		while(i)
		{
			if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}
			i=e[i].next;
		}
	}
	if(h[T]==-1)return 0;
	return 1;
}
int dfs(int x,int f)
{
    if(x==T)return f;
    int i=head[x];
    int w,used=0;
    while(i)
    {
		if(e[i].v&&h[e[i].to]==h[x]+1)
		{
			w=f-used;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;
			e[i^1].v+=w;
			used+=w;
			if(used==f)return f;                      
		}
		i=e[i].next;
	}
    if(!used)h[x]=-1;
    return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);} 
void build(int x)
{
	memset(head,0,sizeof(head));
	cnt=1;
	for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
			if(mp[i][j]==1)insert(S,(i-1)*m+j,1);
	for(int i=2;i<=door;i++)insert(n*m+i,T,x);
	for(int i=2;i<=door;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				if(dis[i][j][k]<=x)insert((j-1)*m+k,n*m+i,x);
}
void search(int k,int x,int y) 
{
	int t=0,w=1,nowx,nowy;
	d[0].x=x;d[0].y=y;
	while(t<w)
	{
		for(int i=0;i<4;i++)
		{   
			nowx=d[t].x+xx[i],nowy=d[t].y+yy[i];
			if(nowx<1||nowy<1||nowx>n||nowy>m||mp[nowx][nowy]!=1)continue;
			if(dis[k][nowx][nowy]==inf)
			{
				dis[k][nowx][nowy]=d[w].s=d[t].s+1;
				d[w].x=nowx;d[w].y=nowy;
				w++; 
			}
		}
		t++;
	}
}
bool judge(int x)
{ 
	build(x);
	ans=0;
	dinic();
	if(ans==tot)return 1;
	return 0; 
}
int main()
{
    scanf("%d%d",&n,&m);
    char ch[21];
    for(int i=1;i<=n;i++)
    {
		scanf("%s",ch);
		for(int j=1;j<=m;j++)
		{
			if(ch[j-1]=='.'){mp[i][j]=1;tot++;}
			else if(ch[j-1]=='D')mp[i][j]=++door; 
		}
	}
    for(int i=2;i<=door;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				dis[i][j][k]=inf;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]>1)search(mp[i][j],i,j);
    int l=0,r=400;
    while(l<=r)
    {
		int mid=(l+r)>>1;
		if(judge(mid)){mn=mid;r=mid-1;}
		else l=mid+1;
	}
    if(mn==-1)printf("impossible");
    else printf("%d",mn);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include<iostream>

#include<cstdio>

#include<cstring>

#define S 0

#define T 1000

#define inf 0x7fffffff

using namespace std;

int n,m,door=1,cnt,ans,tot,mn=-1;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

int mp[21][21],head[1001],h[1001],q[1001];

int dis[401][21][21];

struct data{int x,y,s;}d[401];

struct data2{int to,next,v;}e[1000001];

bool bfs()

{

int t=0,w=1,i,now;

memset(h,-1,sizeof(h));

h[S]=0;q[0]=S;

while(t<w)

{

now=q[t];t++;

i=head[now];

while(i)

{

if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}

i=e[i].next;

}

if(h[T]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int i=head[x];

int w,used=0;

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans+=dfs(0,inf);}

void ins(int u,int v,int w)

{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,0);}

void build(int x)

{

memset(head,0,sizeof(head));

cnt=1;

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

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

if(mp[i][j]==1)insert(S,(i-1)*m+j,1);

for(int i=2;i<=door;i++)insert(n*m+i,T,x);

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

for(int j=1;j<=n;j++)

for(int k=1;k<=m;k++)

if(dis[i][j][k]<=x)insert((j-1)*m+k,n*m+i,x);

}

void search(int k,int x,int y)

{

int t=0,w=1,nowx,nowy;

d[0].x=x;d[0].y=y;

while(t<w)

{

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

{

nowx=d[t].x+xx[i],nowy=d[t].y+yy[i];

if(nowx<1||nowy<1||nowx>n||nowy>m||mp[nowx][nowy]!=1)continue;

if(dis[k][nowx][nowy]==inf)

{

dis[k][nowx][nowy]=d[w].s=d[t].s+1;

d[w].x=nowx;d[w].y=nowy;

w++;

}

t++;

}

bool judge(int x)

{

build(x);

ans=0;

dinic();

if(ans==tot)return 1;

return 0;

}

int main()

{

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

char ch[21];

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

{

scanf("%s",ch);

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

{

if(ch[j-1]=='.'){mp[i][j]=1;tot++;}

else if(ch[j-1]=='D')mp[i][j]=++door;

}

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

for(int j=1;j<=n;j++)

for(int k=1;k<=m;k++)

dis[i][j][k]=inf;

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

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

if(mp[i][j]>1)search(mp[i][j],i,j);

int l=0,r=400;

while(l<=r)

{

int mid=(l+r)>>1;

if(judge(mid)){mn=mid;r=mid-1;}

else l=mid+1;

}

if(mn==-1)printf("impossible");

else printf("%d",mn);

return 0;

}

« 「CODEVS1537」血色先锋队「网络流24题」魔术球问题 »

sxb_201

学长这个代码被X了！！！

hzwer

是的，后来没去重写

xindubawukong

您这样建图有点问题吧，似乎不能处理两个人同时在最后时刻赶到一个门的情况。
学长能指教下吗？

hzwer

这会有什么问题么。。。

xindubawukong

4 5
XXDXX
XX.XX
X…X
XXDXX
比如这组数据，您的代码返回2，实际上答案应该是3

hzwer

噢好像是这样的。。那么就对每个门按时间拆点一下吧

hzwer.com _ Home | http://hzwer.com

「BZOJ1189」[HNOI2007] 紧急疏散evacuate

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论