关于删边最短路问题的若⼲见解
关于最短哥问题的若⼲见解
马鑫宇
1.不缩点的做法
⾸先，对于⼀个图，我们从S点和T点进⾏两次搜索其到所有顶点的最短路，这些最短路定向后将构成两个定向树（不唯⼀时，任取其⼀），根分别为S（出发根）和T（到着根），我们称之为S树和T树。对于两个树，我们分别维护其顶点u的深度为dS[u]和dT[u]。最⼀开始没有任何删边之前就可以在最短路中⽤到的边称之为原边，其他边称之为备择边，视实际需要这两个词可能会有不同含义。
现在我们只考虑S树⽽⽆视T树。那么显然每当删去S-T路之外的边时我们直接输出最短路即可，⽽删除S-T路上的边(i,j)（割边）时，T将被隔离在S树的某⼀个⼦树中。将(i,j)之外的S树上的边视为原边，不在S树上⽽能连接被割断的S树和T所在⼦树的边视为备择边。那么显然，删边后的最短路（备择最短路）⼀定过⾄少⼀条备择边。现在我们证明备择最短路⼀定只过⼀个备择边。
定理1：对任意的割边(i,j)，⼀定存在⼀条备择最短路（可能不唯⼀），使存在被割S树上的点u和T⼦树上的点v，使得备择最短路表⽰为如下结构：S出发经被割S树上的边
到u，备择边(u,v)，v出发经T树上的点到T；因⽽其长度为dS[u]+dT[v]+w[u,v]（⽂中所有定理均假定备择最短路存在）
证明：假设备择最短路为L，且长度⼩于所有满⾜上⾯性质的路。显见L中必定存在⾄少⼀条备择边(u,v)，否则割边(i,j)将⽆法构成S-T割，因为只有T存在于被割S树中才有这种情况，⽽此时S树上S-T路未被(i,j)割断。我们取(u,v)为最后经过的备择边。现在取新路L2如下：S出发经原边到达u，(u,v)，v出发经T树边到达T。显见L2路径长度不超过L，因为将L拆成3部分：S-u，u-v，v-T后，由最⼩树性质，其对应部分长度⼀定不⼩于L2对应部分的长度。注意因为v和T在被割后相同的S树的⼦树中，因此T树中v到T的路不会被(i,j)割断，如若不然则有下图：
⽐较i,j,v三点间的最短路即可得出。L2违背了原假设，因此⽤反证法得出此定理的前半部分。后半部分显⽽易见。
显见不在S树中的任何⼀条边都有机会称为备择边，于
是我们得出枚举备择边的初步想法。取LCA为S树上的最近公共祖先，进⼀步地，我们得出以下定理：
定理2：若(i,j)割的备择最短路经过备择边(u,v)，则⼀定有(i,j)在LCA(u,T)到LCA(v,T)的原路上。
证明：显见若不满⾜此条件，则(u,v)必然在割掉(i,j)之后的同⼀个⼦树上，因此不构成备择边。
综上，我们得出以下算法（备择边-LCA-线段树法）：
1.构建S树，计算所有dS和dT，⽤Tarjan算法初始化LCA
2.对S-T原最短路上的原边维护最⼩值线段树，将每⼀条不在S树上的⽆向边(u,v)拆成⼀对有向边计算其存在于备择最短路上时备择最短路的长度，更新区间[LCA(u,T),LCA(v,T)]
3.对每次查询，返回其在线段树上对应点的值即是结果侧边值问题一定要用正则化吗
（此算法来⾃于[1]，详细细节请参见[1]）
依据线段树的摊还复杂度，此算法时间复杂度预估为O((m+Q)lgm)
如果同时考虑S树和T树，我们可以得出以下定理：
定理3：对于每个(i,j)割边，⼀定存在这样⼀条备择最短路L，使存在顶点u（备择点）将L分成两个部分：S经S 树边到u，和u 经T树边到T。此路径长度为dS[u]+dT[u]。
证明：显⽽易见，此处略去。
定义LCAT和LCAS分别表⽰T树和S树的最近公共祖先。显见某点u成为备择点仅仅在[LCAT(S,u),LCAS(T,u)]区间内才有可能。
因此我们得到以下算法（备择点-LCA-线段树法）：
1.构建S树和T树，计算所有dS和dT，⽤Tarjan算法初始化LCAS和LCAT
2.对S-T原最短路上的原边维护最⼩值线段树，对每⼀个不在S-T原最短路上的点u，计算其在备择最短路上时的备择最短路长度，更新区间[LCAT(u,S),LCAS(u,T)]
3.对每次查询，返回其在线段树上对应点的值即是结果
（此算法来⾃于本⼈⽐赛后的随感）
依据线段树的摊还复杂度，此算法时间复杂度预估为O((n+Q)lgm)，但⽬测不如前⼀个算法⾼效。
2.强连通缩点法
这种做法是出题⼈Vani有约会本⼈给出的解答（[4]），思路⽆误但是标程被质疑（见[2]），其本⼈认为的复杂度为O(nlgn)，但根据其代码分析，应该为O(mlgm)。
定义由S出发的SP图如下：有向边(i,j)属于SP当且仅当⽆向边(i,j)满⾜dS[i]+w[i,j]=dS[j]。易见此图为有向⽆环图。
定义到达T的TP图如下：有向边(i,j)属于TP当且仅当⽆向边(i,j)满⾜dT[j]+w[i,j]=dT[i]。定义S到T的ST图如下：有向边(i,j)属于ST当且仅当⽆向边(i,j)满⾜dS[i]+w[i,j]+dT[j]=dS[T]。
定理4：(1)ST图是SP图和TP图的⼦图。(2)如果所有边权⼤于0，则SP图中不含有向圈。（证明略）
定义SP图中的关键边(i,j)如下：删除(i,j)后，在SP中S 不能到达j点。ST中的关键边类似。我们有
定理5：ST图的关键边是边⽆向化后的桥。SP图的关键边包括但不限于⽆向化后的桥。
证明：我们⾸先证明第⼆个。取图如下：
令S=1,T=3。显见SP图定向边集{(1,2),(2,3),(3,4),(1,4)}，关键边集{(1,2),(2,3)}，但⽆向化之后的图即为原图，三个连通度全为2，证完。
然后在证明第⼀个，假设ST图中的边(i,j)是关键边，但不是⽆向化后的桥。因此删去边(i,j)后，任意取⼀条⽆向化ST图中的S-T 路L，其中必定包括⼀条边(u,v)，其在ST图
中是反向的。不妨设这样的边只有⼀条，因为⼤于⼀条时我们可以逐⼀处理。这意味着S经某条路径L’到达v后再经过(v,u)到达u和S经路L到达u其距离是相等的（定理4）。因为所有边权值为正，故S经路L到达u必定不经过(v,u)。L’中⼀定包括边(i,j)，否则可以直接取L’和L中v到达T的部分得到⼀条S到达T的不包括边(i,j)的路，和(i,j)为关键边⽭盾。⽽S到达u的路⼀定不包含边(i,j)。
现在考虑(v,u)是ST图中的边，意味着dS[v]+dT[u]+w[v,u]=dS[T]。根据dS[v]+w[v,u]=dS[u]（定理4）得到dS[u]+dT[u]=dS[T]。如果原图中存在⼀条u到T的最短路不包括(u,v)⽆向边的话，那么这条最短路的长度⼀定是dT[u]，因⽽这条最短路会出现在ST 图中，因此这条路⼀定经过(i,j)，否则(i,j)不是割边。但这是不可能的，因为之前我们已经到⼀条包括(i,j)的到达v点的路，这样我们就得到了⼀个有向圈u->……->i->j->……->v->u。但是原图中有⼀条u到T的最短路包括(u,v)同样是不可能的，因为这将
导致ST图中包括边(u,v)（根据SP图、TP图、ST图的定义推导即可），从⽽产⽣对称弧(u,v)和(v,u)。⽤反证法可得出此定理成⽴。
在此基础上，我们依据ST图中的关键边对SP图进⾏收缩。因为只有ST图中的关键边被删除时才会导致最短路长度发⽣变化，因此我们定义ST图中的关键边为关键割（关
键割在其他图中不等于关键边）。对SP图，考虑其所有所有⾮关键割的边，我们利⽤这些边进⾏收缩，因此称之为可收缩边。收缩的⽅式如下：沿S到T的最短路排序并遍历其上的顶点i，将其作为基点，然后对所有收缩边(i,j)，如果j不在i之前的分量中，那么就将j沿(i,j)收缩，将其加⼊i所在的分量中；否则不进⾏收缩，⽽是将边反向成(j,i)。在原图中⽽不在SP图中的⽆向边也加⼊到图中，并且按分量的递增⽅向定向。这样我们就得到了收缩后的图SG图。SG图中的边⼀部分是收缩后的，位于同⼀分量内，为收缩边；另⼀部分并没有收缩，成为了备择边。
定理6：(1)对SG图中的每⼀个分量，其基点i可以经过分量中的某条路到达该分量中的任⼀点j，且该路是原图中S到点j的最短路的⼀部分。(2)每⼀个可以从S到达的点都存在于SG图中的分量上。
证明：显见，不证。
定理7：对分量A,B，A在B之前，则对B中任⼀顶点v，原图中A的基点u到其的⼀条最短路经过A到B的全部关键割。
证明：⾸先，设B的基点为p，那么u到p的最短路显然经过关键割，否则和关键割是ST图中桥边的性质不符。因此取从u经过关键割到达p，然后再在同⼀分量内从p到v，这样的到的路径⼀定是最短路径。
定理8：删除某关键割(i,j)后，设j所在分量为A，则对A及A之后的任意分量内的点v，其到T的最短距离不受删边影响。
证明：如果v到T的最短路包含⽆向边(i,j)，那么有向边(j,i)⼀定在图TP中，⼜因为(i,j)在图TP中（定理4），因此TP中存在圈（对称弧），⽭盾。
定理9：删除某关键割(i,j)后，我们⼀定能到⼀条备择最短路满⾜下⾯的性质：其第⼀部分是S到某分量A中的⼀点u，⽽A为i 的分量或之前；第⼆部分是备择边(u,v)，v 所在的分量为j的分量或之后；第三部分是v到T的最短路。
证明：由定理8，所有满⾜性质的路⼀定是不经过(i,j)的S-T路。按照定理1类似的证明⽅法即可得证。
这样我们就得到了第三种算法（关键边缩点-备择边堆维护法）：
1.计算所有的dS,dT，构建SP图。
2.通过SP图计算ST图中的关键边（关键割），缩点得到SG图。
3.建⽴空堆，然后按次序遍历各个关键割和分量。当遍历到关键割(i,j)时，删除所有到达i分量的备择边，然后加⼊所有从j分量出发的备择边，取出堆中的最⼩值为备择最短路长。
4.对不删除关键割的查询，返回原始最短路长。
3.参考⽂献
[1]两道有关删边后最短路径维护的猥琐题（www.doczj/doc/ff2c0656ee06eff9aff8074e.html
/MatoNo1/archive/2013/01/19/1 97399.html）
[2]BZOJ2725的⼀些说明（www.doczj/doc/ff2c0656ee06eff9aff8074e.html /wwwaaannngggrs/item/901b51d115 72a5be33db9011）
[3]故乡的梦——最短路图+双连通分量+堆维护（www.doczj/doc/ff2c0656ee06eff9aff8074e.html
/lydrainbowcat/item/9ac512774710bd 12d1dcb3bb）
[4]Violet VI⽐赛预告（最终话）（www.doczj/doc/ff2c0656ee06eff9aff8074e.html
/__vani/item/ecc63f3527395283c2cf2 945）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。