AC. 梦想

frank_c1

[BZOJ 1822] 冷冻波

发布于2016年03月19日 | 暂无评论 | 569阅读 | 最大流

题目描述

WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以瞬间杀灭一个小精灵。 在森林里有N个巫妖,每个巫妖释放Frozen Nova之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道,若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?

输入格式

输入文件第一行包含三个整数N、M、K(N,M,K<=200),分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来N行,每行包含四个整数x, y, r, t,分别代表了每个巫妖的坐标、攻击范围和施法间隔(单位为秒)。 再接下来M行,每行两个整数x, y,分别代表了每个小精灵的坐标。 再接下来K行,每行三个整数x, y, r,分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过10000,半径和施法间隔不超过20000。

输出格式

输出一行,为消灭所有小精灵的最短时间(以秒计算)。如果永远无法消灭所有的小精灵,则输出-1。

题目解析

十分不喜欢这种网络流还夹杂着奇怪的计算几何的题目。

先预处理巫妖i能否杀掉小精灵j\;(1 \le i \le n,1 \le j \le m)。这一部分是简单的计算几何,就是判圆所包含的区域与线段是否有交点。先求出圆心到线段所在直线的距离h,若h \gt r,则不存在交点;否则继续判断圆心在线段所在直线上的投影是在线段上还是线段的延长线上,若投影在线段上,则存在交点,否则存在交点的条件是r \gt d,其中d是圆心与线段的最短距离。

下面就是网络流的建模了。首先我们二分t,建模如下:

1.建立超级源ss向每个巫妖i连容量为t / a_i + 1的边,a_i是施法间隔;

2.每个巫妖i向能杀掉的小精灵j连容量为1的边;

3.建立超级汇t,每个小精灵jt连容量为1的边。

然后跑最大流即可。如果最大流= m,则时间t是可行的。