OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2007】紧急疏散

【题目描述】

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

【输入】

输入第一行是由空格隔开的一对正整数N与M,以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D',且字符间无空格。

【输出】

只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出'impossible'(不包括引号)。

【输入样例】

5 5

XXXXX

X...D

XX.XX

X..XX

XXDXX

【输出样例】

3

【题解】

这道题有一个优美的性质,即初始时每个格子恰好只有一个人,也就是说假如存在一个人需要花费t的时间到达某一扇门,那么一定有一个人需要花费恰好t-1的时间到达这扇门。这个条件可以进行一定转化,得出的结论是:当撤离时间为k时,每扇门一定存在一种方案,使得恰好k个人从这里逃离。

于是我们可以bfs预处理出每个人到达每扇门的距离,然后二分答案。把每个人和每扇门都看做一个点,源点向每个人连边,容量为1,每个人向这个时间内能到达的门连边,边权为1,每扇门向汇点连边,边权为时间,跑一遍最大流判断是否等于总人数即可。

【代码】

感觉这题挺有意思~然后1A~

http://paste.ubuntu.com/11721451/

评论

© OI技术宅 | Powered by LOFTER