【BZOJ1189】紧急疏散(二分答案,最大流)
题面
Description
发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。
输入文件第一行是由空格隔开的一对正整数N与M,3<=N <=20,3<=M<=20,以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D',且字符间无空格。
Output
只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出'impossible'(不包括引号)。
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
3
题解
首先预处理出来每个空位置到每个门的距离
然而很容易想到二分一个时间
现在考虑如何建图
首先,如果距离小于给定的时间就可以走到门
那么,就从每个空位连向门就行啦?
当然不行
这样子做就不能达到每秒钟只能出去一个人的限制
所以,拆点
把门拆成时间个
当前点哪个时间到达就连接在那个时间上
同时,每个节点连一个容量为1的边到汇点上表示出去了
因为前面的人是可以留在门口等到接下来再出去
所以从每个拆开的门向下一秒连一个容量为INF的边
#include #include #include #include #include #include #include #include