關(guān)于刪邊最短路問題的若干見解

1、關(guān)于最短哥問題的若干見解馬鑫宇1.不縮點的做法首先，對于一個圖，我們從S點和T點進行兩次搜索其到所有頂點的最短路，這些最短路定向后將構(gòu)成兩個定向樹（不唯一時，任取其一），根分別為S（出發(fā)根）和T（到著根），我們稱之為S樹和T樹。對于兩個樹，我們分別維護其頂點u的深度為dSu和dTu。最一開始沒有任何刪邊之前就可以在最短路中用到的邊稱之為原邊，其他邊稱之為備擇邊，視實際需要這兩個詞可能會有不同含義?，F(xiàn)在我們只考慮S樹而無視T樹。那么顯然每當刪去S-T路之外的邊時我們直接輸出最短路即可，而刪除S-T路上的邊(i,j)（割邊）時，T將被隔離在S樹的某一個子樹中。將(i,j)之外的S樹上的邊視為原邊，

2、不在S樹上而能連接被割斷的S樹和T所在子樹的邊視為備擇邊。那么顯然，刪邊后的最短路（備擇最短路）一定過至少一條備擇邊?，F(xiàn)在我們證明備擇最短路一定只過一個備擇邊。定理1：對任意的割邊(i,j)，一定存在一條備擇最短路（可能不唯一），使存在被割S樹上的點u和T子樹上的點v，使得備擇最短路表示為如下結(jié)構(gòu)：S出發(fā)經(jīng)被割S樹上的邊到u，備擇邊(u,v)，v出發(fā)經(jīng)T樹上的點到T；因而其長度為dSu+dTv+wu,v（文中所有定理均假定備擇最短路存在）證明：假設(shè)備擇最短路為L，且長度小于所有滿足上面性質(zhì)的路。顯見L中必定存在至少一條備擇邊(u,v)，否則割邊(i,j)將無法構(gòu)成S-T割，因為只有T存在于被割

3、S樹中才有這種情況，而此時S樹上S-T路未被(i,j)割斷。我們?nèi)?u,v)為最后經(jīng)過的備擇邊。現(xiàn)在取新路L2如下：S出發(fā)經(jīng)原邊到達u，(u,v)，v出發(fā)經(jīng)T樹邊到達T。顯見L2路徑長度不超過L，因為將L拆成3部分：S-u，u-v，v-T后，由最小樹性質(zhì)，其對應部分長度一定不小于L2對應部分的長度。注意因為v和T在被割后相同的S樹的子樹中，因此T樹中v到T的路不會被(i,j)割斷，如若不然則有下圖：比較i,j,v三點間的最短路即可得出。L2違背了原假設(shè)，因此用反證法得出此定理的前半部分。后半部分顯而易見。顯見不在S樹中的任何一條邊都有機會稱為備擇邊，于是我們得出枚舉備擇邊的初步想法。取LCA為

4、S樹上的最近公共祖先，進一步地，我們得出以下定理：定理2：若(i,j)割的備擇最短路經(jīng)過備擇邊(u,v)，則一定有(i,j)在LCA(u,T)到LCA(v,T)的原路上。證明：顯見若不滿足此條件，則(u,v)必然在割掉(i,j)之后的同一個子樹上，因此不構(gòu)成備擇邊。綜上，我們得出以下算法（備擇邊-LCA-線段樹法）：1.構(gòu)建S樹，計算所有dS和dT，用Tarjan算法初始化LCA2.對S-T原最短路上的原邊維護最小值線段樹，將每一條不在S樹上的無向邊(u,v)拆成一對有向邊計算其存在于備擇最短路上時備擇最短路的長度，更新區(qū)間LCA(u,T),LCA(v,T)3.對每次查詢，返回其在線段樹上對應

5、點的值即是結(jié)果（此算法來自于1，詳細細節(jié)請參見1）依據(jù)線段樹的攤還復雜度，此算法時間復雜度預估為O(m+Q)lgm)如果同時考慮S樹和T樹，我們可以得出以下定理：定理3：對于每個(i,j)割邊，一定存在這樣一條備擇最短路L，使存在頂點u（備擇點）將L分成兩個部分：S經(jīng)S樹邊到u，和u經(jīng)T樹邊到T。此路徑長度為dSu+dTu。證明：顯而易見，此處略去。定義LCAT和LCAS分別表示T樹和S樹的最近公共祖先。顯見某點u成為備擇點僅僅在LCAT(S,u),LCAS(T,u)區(qū)間內(nèi)才有可能。因此我們得到以下算法（備擇點-LCA-線段樹法）：1.構(gòu)建S樹和T樹，計算所有dS和dT，用Tarjan算法初始

6、化LCAS和LCAT2.對S-T原最短路上的原邊維護最小值線段樹，對每一個不在S-T原最短路上的點u，計算其在備擇最短路上時的備擇最短路長度，更新區(qū)間LCAT(u,S),LCAS(u,T)3.對每次查詢，返回其在線段樹上對應點的值即是結(jié)果（此算法來自于本人比賽后的隨感）依據(jù)線段樹的攤還復雜度，此算法時間復雜度預估為O(n+Q)lgm)，但目測不如前一個算法高效。2.強連通縮點法這種做法是出題人Vani有約會本人給出的解答（4），思路無誤但是標程被質(zhì)疑（見2），其本人認為的復雜度為O(nlgn)，但根據(jù)其代碼分析，應該為O(mlgm)。定義由S出發(fā)的SP圖如下：有向邊(i,j)屬于SP當且僅當無

7、向邊(i,j)滿足dSi+wi,j=dSj。易見此圖為有向無環(huán)圖。定義到達T的TP圖如下：有向邊(i,j)屬于TP當且僅當無向邊(i,j)滿足dTj+wi,j=dTi。定義S到T的ST圖如下：有向邊(i,j)屬于ST當且僅當無向邊(i,j)滿足dSi+wi,j+dTj=dST。定理4：(1)ST圖是SP圖和TP圖的子圖。(2)如果所有邊權(quán)大于0，則SP圖中不含有向圈。（證明略）定義SP圖中的關(guān)鍵邊(i,j)如下：刪除(i,j)后，在SP中S不能到達j點。ST中的關(guān)鍵邊類似。我們有定理5：ST圖的關(guān)鍵邊是邊無向化后的橋。SP圖的關(guān)鍵邊包括但不限于無向化后的橋。證明：我們首先證明第二個。取圖如下：

8、令S=1,T=3。顯見SP圖定向邊集(1,2),(2,3),(3,4),(1,4)，關(guān)鍵邊集(1,2),(2,3)，但無向化之后的圖即為原圖，三個連通度全為2，證完。然后在證明第一個，假設(shè)ST圖中的邊(i,j)是關(guān)鍵邊，但不是無向化后的橋。因此刪去邊(i,j)后，任意取一條無向化ST圖中的S-T路L，其中必定包括一條邊(u,v)，其在ST圖中是反向的。不妨設(shè)這樣的邊只有一條，因為大于一條時我們可以逐一處理。這意味著S經(jīng)某條路徑L到達v后再經(jīng)過(v,u)到達u和S經(jīng)路L到達u其距離是相等的（定理4）。因為所有邊權(quán)值為正，故S經(jīng)路L到達u必定不經(jīng)過(v,u)。L中一定包括邊(i,j)，否則可以直接

9、取L和L中v到達T的部分得到一條S到達T的不包括邊(i,j)的路，和(i,j)為關(guān)鍵邊矛盾。而S到達u的路一定不包含邊(i,j)?，F(xiàn)在考慮(v,u)是ST圖中的邊，意味著dSv+dTu+wv,u=dST。根據(jù)dSv+wv,u=dSu（定理4）得到dSu+dTu=dST。如果原圖中存在一條u到T的最短路不包括(u,v)無向邊的話，那么這條最短路的長度一定是dTu，因而這條最短路會出現(xiàn)在ST圖中，因此這條路一定經(jīng)過(i,j)，否則(i,j)不是割邊。但這是不可能的，因為之前我們已經(jīng)找到一條包括(i,j)的到達v點的路，這樣我們就得到了一個有向圈u->->i->j->->

10、;v->u。但是原圖中有一條u到T的最短路包括(u,v)同樣是不可能的，因為這將導致ST圖中包括邊(u,v)（根據(jù)SP圖、TP圖、ST圖的定義推導即可），從而產(chǎn)生對稱弧(u,v)和(v,u)。用反證法可得出此定理成立。在此基礎(chǔ)上，我們依據(jù)ST圖中的關(guān)鍵邊對SP圖進行收縮。因為只有ST圖中的關(guān)鍵邊被刪除時才會導致最短路長度發(fā)生變化，因此我們定義ST圖中的關(guān)鍵邊為關(guān)鍵割（關(guān)鍵割在其他圖中不等于關(guān)鍵邊）。對SP圖，考慮其所有所有非關(guān)鍵割的邊，我們利用這些邊進行收縮，因此稱之為可收縮邊。收縮的方式如下：沿S到T的最短路排序并遍歷其上的頂點i，將其作為基點，然后對所有收縮邊(i,j)，如果j不在i

11、之前的分量中，那么就將j沿(i,j)收縮，將其加入i所在的分量中；否則不進行收縮，而是將邊反向成(j,i)。在原圖中而不在SP圖中的無向邊也加入到圖中，并且按分量的遞增方向定向。這樣我們就得到了收縮后的圖SG圖。SG圖中的邊一部分是收縮后的，位于同一分量內(nèi)，為收縮邊；另一部分并沒有收縮， 成為了備擇邊。定理6：(1)對SG圖中的每一個分量，其基點i可以經(jīng)過分量中的某條路到達該分量中的任一點j，且該路是原圖中S到點j的最短路的一部分。(2)每一個可以從S到達的點都存在于SG圖中的分量上。證明：顯見，不證。定理7：對分量A,B，A在B之前，則對B中任一頂點v，原圖中A的基點u到其的一條最短路經(jīng)過A

12、到B的全部關(guān)鍵割。證明：首先，設(shè)B的基點為p，那么u到p的最短路顯然經(jīng)過關(guān)鍵割，否則和關(guān)鍵割是ST圖中橋邊的性質(zhì)不符。因此取從u經(jīng)過關(guān)鍵割到達p，然后再在同一分量內(nèi)從p到v，這樣的到的路徑一定是最短路徑。定理8：刪除某關(guān)鍵割(i,j)后，設(shè)j所在分量為A，則對A及A之后的任意分量內(nèi)的點v，其到T的最短距離不受刪邊影響。證明：如果v到T的最短路包含無向邊(i,j)，那么有向邊(j,i)一定在圖TP中，又因為(i,j)在圖TP中（定理4），因此TP中存在圈（對稱?。?，矛盾。定理9：刪除某關(guān)鍵割(i,j)后，我們一定能找到一條備擇最短路滿足下面的性質(zhì)：其第一部分是S到某分量A中的一點u，而A為i的分量或之前；第二部分是備擇邊(u,v)，v所在的分量為j的分量或之后；第三部分是v到T的最短路。證明：由定理8，所有滿足性質(zhì)的路一定是不經(jīng)過(i,j)的S-T路。按照定理1類似的證明方法即可得證。這樣我們就得到了第三種算法（關(guān)鍵邊縮點-備擇邊堆維護法）：1.計算所有的dS,dT，構(gòu)建SP圖。2.通過SP圖計算ST圖中的關(guān)鍵邊（關(guān)鍵割）