AC. 梦想

frank_c1

[WC 2013] 平面图

发布于2016年12月21日 | 暂无评论 | 582阅读 | 图论

题意简述

给定n个点m条边的连通平面图,边有权值。

现在有q个询问。求连接平面上两点的一条曲线,不能经过无穷大区域,且曲线经过边的最大权值尽量小,询问最小值。

保证询问的点不在平面图的点和边上,且询问点的坐标是0.5的奇数倍,平面图点的坐标是0.5的偶数倍。

5 \le n, m \le 10 ^ 5, 1 \le q \le 10 ^ 5,坐标在[0, 10 ^ 7]范围内。

题目解析

应该可以归为一类比较难写的题目吧。

这题算法思想是不难的。通过初步的分析,我们发现最后的询问就是一个货车运输的模型,没有什么技术含量。难点在于平面图转对偶图点定位上。我们来讨论一下如何实现这两个转化。

平面图转对偶图。学习了xhr神犇的解题报告,发现最左转边的方法好妙哇~ 就是一个简短的DFS啦。

点定位。由于梯形剖分太鬼畜,实在不想学习,还是写扫描线吧。我们考虑保留所有指向x轴正方向的边,将所有的点排序,在扫到某个关键点的时候,就把所有它的入边删去,把它的出边插入,维护边上方的区域编号;在扫到某个询问点的时候,就在平衡树中找到对应的线段即可定位。具体可以看代码。

时间复杂度O((n+q) \log n + m)

来吐槽一些坑点:

1. 无穷大的区域不能经过。

2. 平衡树千万不要复杂度写萎啊。

3. 平面图可能是一棵树或者一条链哦。

总之就是,模块特多,写得时候头脑一定要保持清醒。膜拜出题人,您为何要出这样的题目给大家愉悦哇……