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

发布于 14 天前  24 次阅读


本文章由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 一枚