[BZOJ1189/Luogu3191][HNOI2007]紧急疏散evacuate(二分,网络流)

发布于 2018-02-04  197 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1189/Luogu3191][HNOI2007]紧急疏散evacuate(二分,网络流)

Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

Http

BZOJ
Luogu

Tag

二分,网络流

解决思路

二分时间,转化成判定问题。考虑如何限制每一个门在同一时刻只能出去一个人,若当前二分的时间为\(tim\),则把门拆成\(tim\)个点,每一个点只与汇点连容量为一的边。对于每一个点,练到它能到的门的那个时刻的点,求最大流判断是否为人数。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1189/Luogu3191][HNOI2007]紧急疏散evacuate(二分,网络流)


HNCJ OIer