【图论】线段树优化建图

例如从给某个区间A=[La,Ra]中的所有节点给区间B=[Lb,Rb]的所有节点都分别连接一条权值为w的边,求最短路。

对整个图建两棵线段树A和B。线段树A的内部,小区间走到大区间没有成本,连接0权值的边(象征着放弃小区间的特异性,在包含这个小区间的更大的集合中寻找机会)。线段树B的内部,大区间走到小区间没有成本,连接0权值的边(象征着从大集合中具体到某个小集合)。从线段树B的对应节点走到线段树A的对应节点没有成本,连接权值为0的边(用来和下面的原图边形成一个回路)。

对于原图中的边,为了节省内存(从log^2降低到log),建立虚拟节点P,从线段树A中的log个区间连接到P(边权为w),从P连接到线段树B的log个区间(边权0)。

那么原图中某个节点u到某个v的边,先从u点在A的叶子上升到某个位置,然后经过P转化到目标包含v的集合在B的节点,然后可以选择从B绕行回A重新找机会,或者具体化到v出来。

还是参考个图论高手吧:https://www.cnblogs.com/LadyLex/p/7601119.html

原文地址:https://www.cnblogs.com/purinliang/p/14384194.html