最小生成樹
定義
在閲讀下列內容之前，請務必閲讀 圖論相關概念 與 樹基礎 部分，並瞭解以下定義：
生成子圖
生成樹
我們定義無向連通圖的 最小生成樹 （Minimum Spanning Tree，MST）為邊權和最小的生成樹。
注意：只有連通圖才有生成樹，而對於非連通圖，只存在生成森林。
Kruskal 算法
Kruskal 算法是一種常見並且好寫的最小生成樹算法，由 Kruskal 發明。該算法的基本思想是從小到大加入邊，是個貪心算法。
前置知識
並查集 、貪心 、圖的存儲 。
實現
圖示：
偽代碼：
\[
\begin{array}{ll}
1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v, w) \\
& \text{ denoting that there is an edge between } u \text{ and } v \text{ weighted } w . \\
2 & \textbf{Output. } \text{The edges of the MST of the input graph}.\\
3 & \textbf{Method. } \\
4 & result \gets \varnothing \\
5 & \text{sort } e \text{ into nondecreasing order by weight } w \\
6 & \textbf{for} \text{ each } (u, v, w) \text{ in the sorted } e \\
7 & \qquad \textbf{if } u \text{ and } v \text{ are not connected in the union-find set } \\
8 & \qquad\qquad \text{connect } u \text{ and } v \text{ in the union-find set} \\
9 & \qquad\qquad result \gets result\;\bigcup\ \{(u, v, w)\} \\
10 & \textbf{return } result
\end{array}
\]
算法雖簡單，但需要相應的數據結構來支持……具體來説，維護一個森林，查詢兩個結點是否在同一棵樹中，連接兩棵樹。
抽象一點地説，維護一堆 集合 ，查詢兩個元素是否屬於同一集合，合併兩個集合。
其中，查詢兩點是否連通和連接兩點可以使用並查集維護。
如果使用 \(O(m\log m)\) 的排序算法，並且使用 \(O(m\alpha(m, n))\) 或 \(O(m\log n)\) 的並查集，就可以得到時間複雜度為 \(O(m\log m)\) 的 Kruskal 算法。
證明
思路很簡單，為了造出一棵最小生成樹，我們從最小邊權的邊開始，按邊權從小到大依次加入，如果某次加邊產生了環，就扔掉這條邊，直到加入了 \(n-1\) 條邊，即形成了一棵樹。
證明：使用歸納法，證明任何時候 K 算法選擇的邊集都被某棵 MST 所包含。
基礎：對於算法剛開始時，顯然成立（最小生成樹存在）。
歸納：假設某時刻成立，當前邊集為 \(F\) ，令 \(T\) 為這棵 MST，考慮下一條加入的邊 \(e\) 。
如果 \(e\) 屬於 \(T\) ，那麼成立。
否則，\(T+e\) 一定存在一個環，考慮這個環上不屬於 \(F\) 的另一條邊 \(f\) （一定只有一條）。
首先，\(f\) 的權值一定不會比 \(e\) 小，不然 \(f\) 會在 \(e\) 之前被選取。
然後，\(f\) 的權值一定不會比 \(e\) 大，不然 \(T+e-f\) 就是一棵比 \(T\) 還優的生成樹了。
所以，\(T+e-f\) 包含了 \(F\) ，並且也是一棵最小生成樹，歸納成立。
Prim 算法
Prim 算法是另一種常見並且好寫的最小生成樹算法。該算法的基本思想是從一個結點開始，不斷加點（而不是 Kruskal 算法的加邊）。
實現
圖示：
具體來説，每次要選擇距離最小的一個結點，以及用新的邊更新其他結點的距離。
其實跟 Dijkstra 算法一樣，每次找到距離最小的一個點，可以暴力找也可以用堆維護。
堆優化的方式類似 Dijkstra 的堆優化，但如果使用二叉堆等不支持 \(O(1)\) decrease-key 的堆，複雜度就不優於 Kruskal，常數也比 Kruskal 大。所以，一般情況下都使用 Kruskal 算法，在稠密圖尤其是完全圖上，暴力 Prim 的複雜度比 Kruskal 優，但 不一定 實際跑得更快。
暴力：\(O(n^2+m)\) 。
二叉堆：\(O((n+m) \log n)\) 。
Fib 堆：\(O(n \log n + m)\) 。
偽代碼：
\[
\begin{array}{ll}
1 & \textbf{Input. } \text{The nodes of the graph }V\text{ ; the function }g(u, v)\text{ which}\\
& \text{means the weight of the edge }(u, v)\text{; the function }adj(v)\text{ which}\\
& \text{means the nodes adjacent to }v.\\
2 & \textbf{Output. } \text{The sum of weights of the MST of the input graph.} \\
3 & \textbf{Method.} \\
4 & result \gets 0 \\
5 & \text{choose an arbitrary node in }V\text{ to be the }root \\
6 & dis(root)\gets 0 \\
7 & \textbf{for } \text{each node }v\in(V-\{root\}) \\
8 & \qquad dis(v)\gets\infty \\
9 & rest\gets V \\
10 & \textbf{while } rest\ne\varnothing \\
11 & \qquad cur\gets \text{the node with the minimum }dis\text{ in }rest \\
12 & \qquad result\gets result+dis(cur) \\
13 & \qquad rest\gets rest-\{cur\} \\
14 & \qquad \textbf{for}\text{ each node }v\in adj(cur) \\
15 & \qquad\qquad dis(v)\gets\min(dis(v), g(cur, v)) \\
16 & \textbf{return } result
\end{array}
\]
注意：上述代碼只是求出了最小生成樹的權值，如果要輸出方案還需要記錄每個點的 \(dis\) 代表的是哪條邊。
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 // 使用二叉堆優化的 Prim 算法。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std ;
const int N = 5050 , M = 2e5 + 10 ;
struct E {
int v , w , x ;
} e [ M * 2 ];
int n , m , h [ N ], cnte ;
void adde ( int u , int v , int w ) { e [ ++ cnte ] = E { v , w , h [ u ]}, h [ u ] = cnte ; }
struct S {
int u , d ;
};
bool operator < ( const S & x , const S & y ) { return x . d > y . d ; }
priority_queue < S > q ;
int dis [ N ];
bool vis [ N ];
int res = 0 , cnt = 0 ;
void Prim () {
memset ( dis , 0x3f , sizeof ( dis ));
dis [ 1 ] = 0 ;
q . push ({ 1 , 0 });
while ( ! q . empty ()) {
if ( cnt >= n ) break ;
int u = q . top (). u , d = q . top (). d ;
q . pop ();
if ( vis [ u ]) continue ;
vis [ u ] = 1 ;
++ cnt ;
res += d ;
for ( int i = h [ u ]; i ; i = e [ i ]. x ) {
int v = e [ i ]. v , w = e [ i ]. w ;
if ( w < dis [ v ]) {
dis [ v ] = w , q . push ({ v , w });
}
}
}
}
int main () {
cin >> n >> m ;
for ( int i = 1 , u , v , w ; i <= m ; ++ i ) {
cin >> u >> v >> w , adde ( u , v , w ), adde ( v , u , w );
}
Prim ();
if ( cnt == n )
cout << res ;
else
cout << "No MST." ;
return 0 ;
}
證明
從任意一個結點開始，將結點分成兩類：已加入的，未加入的。
每次從未加入的結點中，找一個與已加入的結點之間邊權最小值最小的結點。
然後將這個結點加入，並連上那條邊權最小的邊。
重複 \(n-1\) 次即可。
證明：還是説明在每一步，都存在一棵最小生成樹包含已選邊集。
基礎：只有一個結點的時候，顯然成立。
歸納：如果某一步成立，當前邊集為 \(F\) ，屬於 \(T\) 這棵 MST，接下來要加入邊 \(e\) 。
如果 \(e\) 屬於 \(T\) ，那麼成立。
否則考慮 \(T+e\) 中環上另一條可以加入當前邊集的邊 \(f\) 。
首先，\(f\) 的權值一定不小於 \(e\) 的權值，否則就會選擇 \(f\) 而不是 \(e\) 了。
然後，\(f\) 的權值一定不大於 \(e\) 的權值，否則 \(T+e-f\) 就是一棵更小的生成樹了。
因此，\(e\) 和 \(f\) 的權值相等，\(T+e-f\) 也是一棵最小生成樹，且包含了 \(F\) 。
Boruvka 算法
接下來介紹另一種求解最小生成樹的算法——Boruvka 算法。該算法的思想是前兩種算法的結合。它可以用於求解 邊權互不相同 的無向圖的最小生成森林。（無向連通圖就是最小生成樹。）
為了描述該算法，我們需要引入一些定義：
定義 \(E'\) 為我們當前找到的最小生成森林的邊。在算法執行過程中，我們逐步向 \(E'\) 加邊，定義 連通塊 表示一個點集 \(V'\subseteq V\) ，且這個點集中的任意兩個點 \(u\) ，\(v\) 在 \(E'\) 中的邊構成的子圖上是連通的（互相可達）。
定義一個連通塊的 最小邊 為它連向其它連通塊的邊中權值最小的那一條。
初始時，\(E'=\varnothing\) ，每個點各自是一個連通塊：
計算每個點分別屬於哪個連通塊。將每個連通塊都設為「沒有最小邊」。
遍歷每條邊 \((u, v)\) ，如果 \(u\) 和 \(v\) 不在同一個連通塊，就用這條邊的邊權分別更新 \(u\) 和 \(v\) 所在連通塊的最小邊。
如果所有連通塊都沒有最小邊，退出程序，此時的 \(E'\) 就是原圖最小生成森林的邊集。否則，將每個有最小邊的連通塊的最小邊加入 \(E'\) ，返回第一步。
下面通過一張動態圖來舉一個例子（圖源自 維基百科 ）：
當原圖連通時，每次迭代連通塊數量至少減半，算法只會迭代不超過 \(O(\log V)\) 次，而原圖不連通時相當於多個子問題，因此算法複雜度是 \(O(E\log V)\) 的。給出算法的偽代碼：（修改自 維基百科 ）
\[
\begin{array}{ll}
1 & \textbf{Input. } \text{A graph }G\text{ whose edges have distinct weights. } \\
2 & \textbf{Output. } \text{The minimum spanning forest of }G . \\
3 & \textbf{Method. } \\
4 & \text{Initialize a forest }F\text{ to be a set of one-vertex trees} \\
5 & \textbf{while } \text{True} \\
6 & \qquad \text{Find the components of }F\text{ and label each vertex of }G\text{ by its component } \\
7 & \qquad \text{Initialize the cheapest edge for each component to "None"} \\
8 & \qquad \textbf{for } \text{each edge }(u, v)\text{ of }G \\
9 & \qquad\qquad \textbf{if } u\text{ and }v\text{ have different component labels} \\
10 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }u \\
11 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }u \\
12 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }v \\
13 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }v \\
14 & \qquad \textbf{if }\text{ all components'cheapest edges are "None"} \\
15 & \qquad\qquad \textbf{return } F \\
16 & \qquad \textbf{for }\text{ each component whose cheapest edge is not "None"} \\
17 & \qquad\qquad\text{ Add its cheapest edge to }F \\
\end{array}
\]
習題
最小生成樹的唯一性
考慮最小生成樹的唯一性。如果一條邊 不在最小生成樹的邊集中 ，並且可以替換與其 權值相同、並且在最小生成樹邊集 的另一條邊。那麼，這個最小生成樹就是不唯一的。
對於 Kruskal 算法，只要計算為當前權值的邊可以放幾條，實際放了幾條，如果這兩個值不一樣，那麼就説明這幾條邊與之前的邊產生了一個環（這個環中至少有兩條當前權值的邊，否則根據並查集，這條邊是不能放的），即最小生成樹不唯一。
尋找權值與當前邊相同的邊，我們只需要記錄頭尾指針，用單調隊列即可在 \(O(\alpha(m))\) （m 為邊數）的時間複雜度裏優秀解決這個問題（基本與原算法時間相同）。
例題：POJ 1679
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 #include <algorithm>
#include <cstdio>
struct Edge {
int x , y , z ;
};
int f [ 100001 ];
Edge a [ 100001 ];
int cmp ( const Edge & a , const Edge & b ) { return a . z < b . z ; }
int find ( int x ) { return f [ x ] == x ? x : f [ x ] = find ( f [ x ]); }
int main () {
int t ;
scanf ( "%d" , & t );
while ( t -- ) {
int n , m ;
scanf ( "%d%d" , & n , & m );
for ( int i = 1 ; i <= n ; i ++ ) f [ i ] = i ;
for ( int i = 1 ; i <= m ; i ++ ) scanf ( "%d%d%d" , & a [ i ]. x , & a [ i ]. y , & a [ i ]. z );
std :: sort ( a + 1 , a + m + 1 , cmp ); // 先排序
int num = 0 , ans = 0 , tail = 0 , sum1 = 0 , sum2 = 0 ;
bool flag = 1 ;
for ( int i = 1 ; i <= m + 1 ; i ++ ) { // 再并查集加边
if ( i > tail ) {
if ( sum1 != sum2 ) {
flag = 0 ;
break ;
}
sum1 = 0 ;
for ( int j = i ; j <= m + 1 ; j ++ ) {
if ( a [ j ]. z != a [ i ]. z ) {
tail = j - 1 ;
break ;
}
if ( find ( a [ j ]. x ) != find ( a [ j ]. y )) ++ sum1 ;
}
sum2 = 0 ;
}
if ( i > m ) break ;
int x = find ( a [ i ]. x );
int y = find ( a [ i ]. y );
if ( x != y && num != n - 1 ) {
sum2 ++ ;
num ++ ;
f [ x ] = f [ y ];
ans += a [ i ]. z ;
}
}
if ( flag )
printf ( "%d \n " , ans );
else
printf ( "Not Unique! \n " );
}
return 0 ;
}
次小生成樹
非嚴格次小生成樹
定義
在無向圖中，邊權和最小的滿足邊權和 大於等於 最小生成樹邊權和的生成樹
求解方法
求出無向圖的最小生成樹 \(T\) ，設其權值和為 \(M\)
遍歷每條未被選中的邊 \(e = (u,v,w)\) ，找到 \(T\) 中 \(u\) 到 \(v\) 路徑上邊權最大的一條邊 \(e' = (s,t,w')\) ，則在 \(T\) 中以 \(e\) 替換 \(e'\) ，可得一棵權值和為 \(M' = M + w - w'\) 的生成樹 \(T'\) .
對所有替換得到的答案 \(M'\) 取最小值即可
如何求 \(u,v\) 路徑上的邊權最大值呢？
我們可以使用倍增來維護，預處理出每個節點的 \(2^i\) 級祖先及到達其 \(2^i\) 級祖先路徑上最大的邊權，這樣在倍增求 LCA 的過程中可以直接求得。
嚴格次小生成樹
定義
在無向圖中，邊權和最小的滿足邊權和 嚴格大於 最小生成樹邊權和的生成樹
求解方法
考慮剛才的非嚴格次小生成樹求解過程，為什麼求得的解是非嚴格的？
因為最小生成樹保證生成樹中 \(u\) 到 \(v\) 路徑上的邊權最大值一定 不大於 其他從 \(u\) 到 \(v\) 路徑的邊權最大值。換言之，當我們用於替換的邊的權值與原生成樹中被替換邊的權值相等時，得到的次小生成樹是非嚴格的。
解決的辦法很自然：我們維護到 \(2^i\) 級祖先路徑上的最大邊權的同時維護 嚴格次大邊權 ，當用於替換的邊的權值與原生成樹中路徑最大邊權相等時，我們用嚴格次大值來替換即可。
這個過程可以用倍增求解，複雜度 \(O(m \log m)\) 。
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155 #include <algorithm>
#include <iostream>
const int INF = 0x3fffffff ;
const long long INF64 = 0x3fffffffffffffffLL ;
struct Edge {
int u , v , val ;
bool operator < ( const Edge & other ) const { return val < other . val ; }
};
Edge e [ 300010 ];
bool used [ 300010 ];
int n , m ;
long long sum ;
class Tr {
private :
struct Edge {
int to , nxt , val ;
} e [ 600010 ];
int cnt , head [ 100010 ];
int pnt [ 100010 ][ 22 ];
int dpth [ 100010 ];
// 到祖先的路徑上邊權最大的邊
int maxx [ 100010 ][ 22 ];
// 到祖先的路徑上邊權次大的邊，若不存在則為 -INF
int minn [ 100010 ][ 22 ];
public :
void addedge ( int u , int v , int val ) {
e [ ++ cnt ] = ( Edge ){ v , head [ u ], val };
head [ u ] = cnt ;
}
void insedge ( int u , int v , int val ) {
addedge ( u , v , val );
addedge ( v , u , val );
}
void dfs ( int now , int fa ) {
dpth [ now ] = dpth [ fa ] + 1 ;
pnt [ now ][ 0 ] = fa ;
minn [ now ][ 0 ] = - INF ;
for ( int i = 1 ; ( 1 << i ) <= dpth [ now ]; i ++ ) {
pnt [ now ][ i ] = pnt [ pnt [ now ][ i - 1 ]][ i - 1 ];
int kk [ 4 ] = { maxx [ now ][ i - 1 ], maxx [ pnt [ now ][ i - 1 ]][ i - 1 ],
minn [ now ][ i - 1 ], minn [ pnt [ now ][ i - 1 ]][ i - 1 ]};
// 從四個值中取得最大值
std :: sort ( kk , kk + 4 );
maxx [ now ][ i ] = kk [ 3 ];
// 取得嚴格次大值
int ptr = 2 ;
while ( ptr >= 0 && kk [ ptr ] == kk [ 3 ]) ptr -- ;
minn [ now ][ i ] = ( ptr == -1 ? - INF : kk [ ptr ]);
}
for ( int i = head [ now ]; i ; i = e [ i ]. nxt ) {
if ( e [ i ]. to != fa ) {
maxx [ e [ i ]. to ][ 0 ] = e [ i ]. val ;
dfs ( e [ i ]. to , now );
}
}
}
int lca ( int a , int b ) {
if ( dpth [ a ] < dpth [ b ]) std :: swap ( a , b );
for ( int i = 21 ; i >= 0 ; i -- )
if ( dpth [ pnt [ a ][ i ]] >= dpth [ b ]) a = pnt [ a ][ i ];
if ( a == b ) return a ;
for ( int i = 21 ; i >= 0 ; i -- ) {
if ( pnt [ a ][ i ] != pnt [ b ][ i ]) {
a = pnt [ a ][ i ];
b = pnt [ b ][ i ];
}
}
return pnt [ a ][ 0 ];
}
int query ( int a , int b , int val ) {
int res = - INF ;
for ( int i = 21 ; i >= 0 ; i -- ) {
if ( dpth [ pnt [ a ][ i ]] >= dpth [ b ]) {
if ( val != maxx [ a ][ i ])
res = std :: max ( res , maxx [ a ][ i ]);
else
res = std :: max ( res , minn [ a ][ i ]);
a = pnt [ a ][ i ];
}
}
return res ;
}
} tr ;
int fa [ 100010 ];
int find ( int x ) { return fa [ x ] == x ? x : fa [ x ] = find ( fa [ x ]); }
void Kruskal () {
int tot = 0 ;
std :: sort ( e + 1 , e + m + 1 );
for ( int i = 1 ; i <= n ; i ++ ) fa [ i ] = i ;
for ( int i = 1 ; i <= m ; i ++ ) {
int a = find ( e [ i ]. u );
int b = find ( e [ i ]. v );
if ( a != b ) {
fa [ a ] = b ;
tot ++ ;
tr . insedge ( e [ i ]. u , e [ i ]. v , e [ i ]. val );
sum += e [ i ]. val ;
used [ i ] = 1 ;
}
if ( tot == n - 1 ) break ;
}
}
int main () {
std :: ios :: sync_with_stdio ( 0 );
std :: cin . tie ( 0 );
std :: cout . tie ( 0 );
std :: cin >> n >> m ;
for ( int i = 1 ; i <= m ; i ++ ) {
int u , v , val ;
std :: cin >> u >> v >> val ;
e [ i ] = ( Edge ){ u , v , val };
}
Kruskal ();
long long ans = INF64 ;
tr . dfs ( 1 , 0 );
for ( int i = 1 ; i <= m ; i ++ ) {
if ( ! used [ i ]) {
int _lca = tr . lca ( e [ i ]. u , e [ i ]. v );
// 找到路徑上不等於 e[i].val 的最大邊權
long long tmpa = tr . query ( e [ i ]. u , _lca , e [ i ]. val );
long long tmpb = tr . query ( e [ i ]. v , _lca , e [ i ]. val );
// 這樣的邊可能不存在，只在這樣的邊存在時更新答案
if ( std :: max ( tmpa , tmpb ) > - INF )
ans = std :: min ( ans , sum - std :: max ( tmpa , tmpb ) + e [ i ]. val );
}
}
// 次小生成樹不存在時輸出 -1
std :: cout << ( ans == INF64 ? -1 : ans ) << '\n' ;
return 0 ;
}
瓶頸生成樹
定義
無向圖 \(G\) 的瓶頸生成樹是這樣的一個生成樹，它的最大的邊權值在 \(G\) 的所有生成樹中最小。
性質
最小生成樹是瓶頸生成樹的充分不必要條件。 即最小生成樹一定是瓶頸生成樹，而瓶頸生成樹不一定是最小生成樹。
關於最小生成樹一定是瓶頸生成樹這一命題，可以運用反證法證明：我們設最小生成樹中的最大邊權為 \(w\) ，如果最小生成樹不是瓶頸生成樹的話，則瓶頸生成樹的所有邊權都小於 \(w\) ，我們只需刪去原最小生成樹中的最長邊，用瓶頸生成樹中的一條邊來連接刪去邊後形成的兩棵樹，得到的新生成樹一定比原最小生成樹的權值和還要小，這樣就產生了矛盾。
例題
POJ 2395 Out of Hay
給出 n 個農場和 m 條邊，農場按 1 到 n 編號，現在有一人要從編號為 1 的農場出發到其他的農場去，求在這途中他最多需要攜帶的水的重量，注意他每到達一個農場，可以對水進行補給，且要使總共的路徑長度最小。
題目要求的就是瓶頸樹的最大邊，可以通過求最小生成樹來解決。
最小瓶頸路
定義
無向圖 \(G\) 中 x 到 y 的最小瓶頸路是這樣的一類簡單路徑，滿足這條路徑上的最大的邊權在所有 x 到 y 的簡單路徑中是最小的。
性質
根據最小生成樹定義，x 到 y 的最小瓶頸路上的最大邊權等於最小生成樹上 x 到 y 路徑上的最大邊權。雖然最小生成樹不唯一，但是每種最小生成樹 x 到 y 路徑的最大邊權相同且為最小值。也就是説，每種最小生成樹上的 x 到 y 的路徑均為最小瓶頸路。
但是，並不是所有最小瓶頸路都存在一棵最小生成樹滿足其為樹上 x 到 y 的簡單路徑。
例如下圖：
1 到 4 的最小瓶頸路顯然有以下兩條：1-2-3-4。1-3-4。
但是，1-2 不會出現在任意一種最小生成樹上。
應用
由於最小瓶頸路不唯一，一般情況下會詢問最小瓶頸路上的最大邊權。
也就是説，我們需要求最小生成樹鏈上的 max。
倍增、樹剖都可以解決，這裏不再展開。
Kruskal 重構樹
定義
在跑 Kruskal 的過程中我們會從小到大加入若干條邊。現在我們仍然按照這個順序。
首先新建 \(n\) 個集合，每個集合恰有一個節點，點權為 \(0\) 。
每一次加邊會合並兩個集合，我們可以新建一個點，點權為加入邊的邊權，同時將兩個集合的根節點分別設為新建點的左兒子和右兒子。然後我們將兩個集合和新建點合併成一個集合。將新建點設為根。
不難發現，在進行 \(n-1\) 輪之後我們得到了一棵恰有 \(n\) 個葉子的二叉樹，同時每個非葉子節點恰好有兩個兒子。這棵樹就叫 Kruskal 重構樹。
舉個例子：
這張圖的 Kruskal 重構樹如下：
性質
不難發現，原圖中兩個點之間的所有簡單路徑上最大邊權的最小值 = 最小生成樹上兩個點之間的簡單路徑上的最大值 = Kruskal 重構樹上兩點之間的 LCA 的權值。
也就是説，到點 \(x\) 的簡單路徑上最大邊權的最小值 \(\leq val\) 的所有點 \(y\) 均在 Kruskal 重構樹上的某一棵子樹內，且恰好為該子樹的所有葉子節點。
我們在 Kruskal 重構樹上找到 \(x\) 到根的路徑上權值 \(\leq val\) 的最淺的節點。顯然這就是所有滿足條件的節點所在的子樹的根節點。
如果需要求原圖中兩個點之間的所有簡單路徑上最小邊權的最大值，則在跑 Kruskal 的過程中按邊權大到小的順序加邊。
「LOJ 137」最小瓶頸路 加強版 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137 #include <bits/stdc++.h>
using namespace std ;
const int MAX_VAL_RANGE = 280010 ;
int n , m , log2Values [ MAX_VAL_RANGE + 1 ];
namespace TR {
struct Edge {
int to , nxt , val ;
} e [ 400010 ];
int cnt , head [ 140010 ];
void addedge ( int u , int v , int val = 0 ) {
e [ ++ cnt ] = ( Edge ){ v , head [ u ], val };
head [ u ] = cnt ;
}
int val [ 140010 ];
namespace LCA {
int sec [ 280010 ], cnt ;
int pos [ 140010 ];
int dpth [ 140010 ];
void dfs ( int now , int fa ) {
dpth [ now ] = dpth [ fa ] + 1 ;
sec [ ++ cnt ] = now ;
pos [ now ] = cnt ;
for ( int i = head [ now ]; i ; i = e [ i ]. nxt ) {
if ( fa != e [ i ]. to ) {
dfs ( e [ i ]. to , now );
sec [ ++ cnt ] = now ;
}
}
}
int dp [ 280010 ][ 20 ];
void init () {
dfs ( 2 * n - 1 , 0 );
for ( int i = 1 ; i <= 4 * n ; i ++ ) {
dp [ i ][ 0 ] = sec [ i ];
}
for ( int j = 1 ; j <= 19 ; j ++ ) {
for ( int i = 1 ; i + ( 1 << j ) - 1 <= 4 * n ; i ++ ) {
dp [ i ][ j ] = dpth [ dp [ i ][ j - 1 ]] < dpth [ dp [ i + ( 1 << ( j - 1 ))][ j - 1 ]]
? dp [ i ][ j - 1 ]
: dp [ i + ( 1 << ( j - 1 ))][ j - 1 ];
}
}
}
int lca ( int x , int y ) {
int l = pos [ x ], r = pos [ y ];
if ( l > r ) {
swap ( l , r );
}
int k = log2Values [ r - l + 1 ];
return dpth [ dp [ l ][ k ]] < dpth [ dp [ r - ( 1 << k ) + 1 ][ k ]]
? dp [ l ][ k ]
: dp [ r - ( 1 << k ) + 1 ][ k ];
}
} // namespace LCA
} // namespace TR
using TR :: addedge ;
namespace GR {
struct Edge {
int u , v , val ;
bool operator < ( const Edge & other ) const { return val < other . val ; }
} e [ 100010 ];
int fa [ 140010 ];
int find ( int x ) { return fa [ x ] == 0 ? x : fa [ x ] = find ( fa [ x ]); }
void kruskal () { // 最小生成树
int tot = 0 , cnt = n ;
sort ( e + 1 , e + m + 1 );
for ( int i = 1 ; i <= m ; i ++ ) {
int fau = find ( e [ i ]. u ), fav = find ( e [ i ]. v );
if ( fau != fav ) {
cnt ++ ;
fa [ fau ] = fa [ fav ] = cnt ;
addedge ( fau , cnt );
addedge ( cnt , fau );
addedge ( fav , cnt );
addedge ( cnt , fav );
TR :: val [ cnt ] = e [ i ]. val ;
tot ++ ;
}
if ( tot == n - 1 ) {
break ;
}
}
}
} // namespace GR
int ans ;
int A , B , C , P ;
int rnd () { return A = ( A * B + C ) % P ; }
void initLog2 () {
for ( int i = 2 ; i <= MAX_VAL_RANGE ; i ++ ) {
log2Values [ i ] = log2Values [ i >> 1 ] + 1 ;
}
}
int main () {
initLog2 (); // 预处理
cin >> n >> m ;
for ( int i = 1 ; i <= m ; i ++ ) {
int u , v , val ;
cin >> u >> v >> val ;
GR :: e [ i ] = ( GR :: Edge ){ u , v , val };
}
GR :: kruskal ();
TR :: LCA :: init ();
int Q ;
cin >> Q ;
cin >> A >> B >> C >> P ;
while ( Q -- ) {
int u = rnd () % n + 1 , v = rnd () % n + 1 ;
ans += TR :: val [ TR :: LCA :: lca ( u , v )];
ans %= 1000000007 ;
}
cout << ans ;
return 0 ;
}
NOI 2018 歸程 首先預處理出來每一個點到根節點的最短路。
我們構造出來根據海拔的最大生成樹。顯然每次詢問可以到達的節點是在最大生成樹中和詢問點的路徑上最小邊權 \(> p\) 的節點。
根據 Kruskal 重構樹的性質，這些節點滿足均在一棵子樹內同時為其所有葉子節點。
也就是説，我們只需要求出 Kruskal 重構樹上每一棵子樹葉子的權值 min 就可以支持子樹詢問。
詢問的根節點可以使用 Kruskal 重構樹上倍增的方式求出。
時間複雜度 \(O((n+m+Q) \log n)\) 。
更新历史 在 GitHub 上编辑此页！ Chrogeek, Enter-tainer, HeRaNO, Ir1d, Marcythm, ShadowsEpic, StudyingFather, Xeonacid, bear-good, billchenchina, diauweb, diauweb, greyqz, kawa-yoiko, ouuan, partychicken, sshwy, stevebraveman, zhouyuyang2002, renbaoshuo, Hszzzx, y-kx-b CC BY-SA 4.0 和 SATA
