BZOJ 3073 [Pa2011]Journeys


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3073

题意:求一个边数点数很多的无向图最短路,边权为 1...


这题很有意思,下面的题解是之前集训时候写的,有机会会重写一遍...

线段树优化建图最短路... 学到了新姿势
由于 n 很大,直接建图一定无法接受... 但是我们发现数据给出的很有规律 且边权均为 1 原图保证两两点均可达
这样有一个端点相同的边具有很大的相似性...
具体是怎么优化建图的呢? 我们建 2 个线段树,记为树 A,B(接下连边均为单向边
将树 A 中的点连向父亲节点 树 B 中的点连向儿子节点 树 A B 对应的叶子节点相连(有些题解要求树 AB 对应节点均相连 个人认为没有必要 qwq 望斧正
此时从 B 树的任意一个节点都能以 0 的距离到达该节点对应区间在 A 树上的节点
对于给出的加边操作 由于其为无向边 在进行下操作后进行一次反操作
对于每一个操作开一个新点 从 A 树的对应节点连向 B 树的对应节点 权值为 1/2
这样做后 可以抽象 A 树的每个叶子节点为原图中的点啦
为什么可以呢 我们可以结合下图感性 (Y) 理解 (Y) 一下 (图后补
首先在不开新点时 A 树叶子节点是两两不可达的 加入了新点后 A 树叶子节点如果想抵达另一个叶子节点
必须要经过如下流程:A 树-新点-B 树-A 树
那么这样的一条路径就和原图中的一条边一一对应了
A 树中两叶子节点联通当且仅当它们在原图中可以互相抵达
然后就结束了 由于新图边权均为 0/1 可以 bfs 实现线性复杂度... 我比较懒,上了 dijkstra....
另外此题略卡空间... 调了几发才过..

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3073 [Pa2011]Journeys


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,