1.非嚴(yán)格次小生成樹(shù)
? ? 結(jié)論:非嚴(yán)格次小生成樹(shù)與MST只差一條邊.
? ? 做法：求出MST。對(duì)于每一條不在生成樹(shù)的邊，加入到樹(shù)中一定會(huì)成環(huán).那么刪除 除該邊以外最大權(quán)值的邊.得到新的價(jià)值,?
.
? ? 具體算法：?
? ? ? ? ? ? 1.跑一遍kursal算法咆瘟。得到MST的價(jià)值V
? ? ? ? ? ? 2.對(duì)MST跑倍增算法，維護(hù)k級(jí)祖先以及到其的最大邊權(quán).
? ? ? ? ? ? 3.對(duì)于每一條不在MST的邊E.查詢(xún)兩個(gè)點(diǎn)(u,v)之間的最大值res(這個(gè)可以在求LCA的過(guò)程中求得). 得到新價(jià)值 Val = V - res + E.len.
? ? ? ? ? ? 4.答案為:min(val)
? ?
相關(guān)應(yīng)用:
1.求一張圖的MST是否唯一.? ? ? ?
????????求次小生成樹(shù)佳窑，判相等即可
2.求必經(jīng)過(guò)某條邊的MST挽封。
? ? ? ? 1.若該邊在MST中.直接輸出V
? ? ? ? 2.若該邊不在MST中，將其加入MST敬惦，替換掉 環(huán)上除它之外的最大邊權(quán)
2.嚴(yán)格次小生成樹(shù)
結(jié)論:嚴(yán)格次小生成樹(shù)與MST只差一條邊.
? ? 原理：只要存在某一條 [不在MST中的邊] 與環(huán)上的最大值相同 時(shí)盼理，上述算法求得的次小生成樹(shù)是不嚴(yán)格的。
? ? 做法：與上面大致相同俄删。多維護(hù)一個(gè)嚴(yán)格次大的邊權(quán)宏怔。 枚舉邊E時(shí)，當(dāng)最大值 == E邊權(quán) 則取次大值. 最后所有結(jié)果要取取最小值畴椰。
?模板題: 洛谷P4180
3.瓶頸生成樹(shù)
定義
無(wú)向圖??的瓶頸生成樹(shù)是這樣的一個(gè)生成樹(shù)臊诊，它的最大的邊權(quán)值在??的所有生成樹(shù)中最小。
?結(jié)論:最小生成樹(shù)一定是瓶頸生成樹(shù)斜脂，而瓶頸生成樹(shù)不一定是最小生成樹(shù)妨猩。
4.最小瓶頸路
定義
無(wú)向圖??中 x 到 y 的最小瓶頸路是這樣的一類(lèi)簡(jiǎn)單路徑，滿足這條路徑上的最大的邊權(quán)在所有 x 到 y 的簡(jiǎn)單路徑中是最小的秽褒。
應(yīng)用:
多次查詢(xún) 任意兩點(diǎn) 的 最小瓶頸路 的最大值.? ? ? 處理方法和 次小生成樹(shù) 一樣壶硅。
