[BZOJ3073][PA2011]Journeys(最短路径,线段树)

发布于 2018-05-08  225 次阅读


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

本文链接地址:[BZOJ3073][PA2011]Journeys(最短路径,线段树)

Description

Seter建造了一个很大的星球,他准备建造N个国家和无数双向道路。N个国家很快建造好了,用1..N编号,但是他发现道路实在太多了,他要一条条建简直是不可能的!于是他以如下方式建造道路:(a,b),(c,d)表示,对于任意两个国家x,y,如果a<=x<=b,c<=y<=d,那么在xy之间建造一条道路。Seter保证一条道路不会修建两次,也保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路,他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然,Seter保证P号国家能到任意一个国家。

Tag

最短路径,线段树

解决思路

如果数据范围小一点的话,那么这就是最短路径的题。但由于是区间连边,最坏情况下边数可能到达爆炸的$$O(n^2m)$$,所以考虑优化连边。
由区间可以想到处理区间的利器——线段树。对于双向路径$(a,b)-(c,d)$,我们把它拆成两条单向的路径。对于每一组$(a,b)->(c,d)$,我们新建立一个虚点$node$,然后考虑如何建图。
单个一棵线段树是无法处理双向边的问题的,不妨建立两棵线段树,一棵成为出线段树,即$(a,b)->node$,反之,另一颗为入线段树。建边如下。
首先是线段树上的建边。对于出线段树,从儿子指向父亲,表示若能到达儿子,则也能到达父亲,权为0;对于入线段树,从父亲指向儿子,表示若能到达父亲,也能到达儿子,权为0;另外再从入线段树的点直到对应出线段树的节点,权为0。
然后是$$(a,b)->(c,d)$$。在出线段树上找到$(a,b)$对应的$log$个区间,分别从这些区间连到$node$,权为$1$;再在入线段树上找到$(c,d)$对应的$log$个区间,从$node$连边到这些区间,权为$0$。
然后跑最短路,最后的答案就在每一个点对应的第一棵线段树的节点上。

代码

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

本文链接地址:[BZOJ3073][PA2011]Journeys(最短路径,线段树)


HNCJ OIer