Skip to content

Minimum Spanning Tree

Definition

Before reading the following content, please be sure to read the Graph Theory Related Concepts and Tree Basics sections, and understand the following definitions:

  1. Spanning subgraph
  2. Spanning tree

We define the Minimum Spanning Tree (MST) of an undirected connected graph as the spanning tree with the minimum sum of edge weights.

Note: Only connected graphs have spanning trees, while for disconnected graphs, only spanning forests exist.

Kruskal's Algorithm

Kruskal's algorithm is a common and easy-to-write minimum spanning tree algorithm, invented by Kruskal. The basic idea of the algorithm is to add edges from smallest to largest, making it a greedy algorithm.

Prerequisites

Disjoint Set Union (DSU), Greedy, Graph Storage.

Implementation

Illustration:

Pseudocode:

\[ \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} \]

Although the algorithm is simple, it requires appropriate data structures to support it... Specifically, maintain a forest, query whether two nodes are in the same tree, and connect two trees.

More abstractly, maintain a collection of sets, query whether two elements belong to the same set, and merge two sets.

Among these, querying whether two points are connected and connecting two points can be maintained using a disjoint set union.

If an \(O(m\log m)\) sorting algorithm is used, along with an \(O(m\alpha(m, n))\) or \(O(m\log n)\) disjoint set union, a Kruskal's algorithm with time complexity \(O(m\log m)\) can be obtained.

Proof

The idea is simple: to construct a minimum spanning tree, we start from the edge with the smallest weight and add edges in increasing order of weight. If adding an edge creates a cycle, discard that edge. Continue until \(n-1\) edges are added, forming a tree.

Proof: Use induction to prove that at any time, the edge set selected by Kruskal's algorithm is contained in some MST.

Base case: At the start of the algorithm, it obviously holds (a minimum spanning tree exists).

Inductive step: Assume it holds at some moment, with the current edge set \(F\). Let \(T\) be this MST, and consider the next edge \(e\) to be added.

If \(e\) belongs to \(T\), then it holds.

Otherwise, \(T+e\) must contain a cycle. Consider another edge \(f\) on this cycle that does not belong to \(F\) (at least one exists).

First, the weight of \(f\) cannot be less than that of \(e\); otherwise, \(f\) would have been selected before \(e\).

Second, the weight of \(f\) cannot be greater than that of \(e\); otherwise, \(T+e-f\) would be a spanning tree better than \(T\).

Thus, \(T+e-f\) contains \(F\) and is also a minimum spanning tree, completing the induction.

Example

Luogu P1195 Pocket Sky

There are \(n\) clouds, and you need to connect them into \(k\) cotton candies. Connecting cloud \(X_i\) and \(Y_i\) requires a cost of \(L_i\). Find the minimum total cost.

Example Code 
 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
#include <algorithm>
#include <iostream>
using namespace std;

int fa[1010];  // Define parent array
int n, m, k;

struct edge {
  int u, v, w;
};

int l;
edge g[10010];

void add(int u, int v, int w) {
  l++;
  g[l].u = u;
  g[l].v = v;
  g[l].w = w;
}

// Standard Union-Find
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }

void Merge(int x, int y) {
  x = findroot(x);
  y = findroot(y);
  fa[x] = y;
}

bool cmp(edge A, edge B) { return A.w < B.w; }

// Kruskal's algorithm
void kruskal() {
  int tot = 0;  // Store the number of selected edges
  int ans = 0;  // Store the total cost
  for (int i = 1; i <= m; i++) {
    int xr = findroot(g[i].u), yr = findroot(g[i].v);
    if (xr != yr) {        // If parents are different
      Merge(xr, yr);       // Merge
      tot++;               // Increase edge count
      ans += g[i].w;       // Increase cost
      if (tot == n - k) {  // Check if selected edges meet k marshmallows
        cout << ans << '\n';
        return;
      }
    }
  }
  cout << "No Answer\n";  // Cannot connect
}

int main() {
  cin >> n >> m >> k;
  if (n == k) {  // Special case boundary condition
    cout << "0\n";
    return 0;
  }
  for (int i = 1; i <= n; i++) {  // Initialize
    fa[i] = i;
  }
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);  // Add edge
  }
  sort(g + 1, g + m + 1, cmp);  // Sort by edge weight first
  kruskal();
  return 0;
}

 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
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w


fa = [0] * 1010  # Define parent array
g = []


def add(u, v, w):
    g.append(Edge(u, v, w))


# Standard Union-Find
def findroot(x):
    if fa[x] == x:
        return x
    fa[x] = findroot(fa[x])
    return fa[x]


def Merge(x, y):
    x = findroot(x)
    y = findroot(y)
    fa[x] = y


# Kruskal's algorithm
def kruskal():
    tot = 0  # Number of edges selected
    ans = 0  # Total cost
    for e in g:
        x = findroot(e.u)
        y = findroot(e.v)
        if x != y:  # If they have different roots
            fa[x] = y  # Merge
            tot += 1  # Increase edge count
            ans += e.w  # Increase cost
            if tot == n - k:  # Check if selected edges meet k marshmallows condition
                print(ans)
                return
    print("No Answer")  # Cannot connect


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    if n == k:  # Special case boundary condition
        print("0")
        exit()
    for i in range(1, n + 1):  # Initialize
        fa[i] = i
    for i in range(1, m + 1):
        u, v, w = map(int, input().split())
        add(u, v, w)  # Add edge
    g.sort(key=lambda edge: edge.w)  # Sort by edge weight first
    kruskal()


 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
```java
import java.util.Arrays;
import java.util.Scanner;

class Edge {
    int u;
    int v;
    int w;

    Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

public class Main {
    static int[] parent = new int[1010];  // Parent array for union-find
    static int m, n, k;  // n: number of vertices, m: number of edges, k: required number of connected components (cotton candies)

    static Edge[] edges = new Edge[10010];
    static int l;

    static void addEdge(int u, int v, int w) {
        edges[++l] = new Edge(u, v, w);
    }

    // Standard union-find find operation
    static int findroot(int x) {
        if (parent[x] != x) {
            parent[x] = findroot(parent[x]);
        }
        return parent[x];
    }

    static void Merge(int x, int y) {
        x = findroot(x);
        y = findroot(y);
        parent[x] = y;
    }

    static boolean cmp(Edge A, Edge B) {
        return A.w < B.w;
    }

    // Kruskal's algorithm
    static void kruskal() {
        int tot = 0;  // Count of selected edges
        int ans = 0;  // Total cost

        for (int i = 1; i <= m; i++) {
            int xr = findroot(edges[i].u);
            int yr = findroot(edges[i].v);
            if (xr != yr) {   // If they are in different components
                Merge(xr, yr); // Merge them
                tot++; // Increment edge count
                ans += edges[i].w; // Add cost
                if (tot == n - k) {  // Check if we have selected enough edges for k components
                    System.out.println(ans);
                    return;
                }
            }
        }
        System.out.println("No Answer");  // Cannot form k connected components
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();

        if (n == k) { // Special case: each vertex is its own component
            System.out.println("0");
            return;
        }

        // Initialization
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            addEdge(u, v, w);  // Add edge
        }
        Arrays.sort(edges, 1, m + 1, (a, b) -> Integer.compare(a.w, b.w));  // Sort edges by weight
        kruskal();
        scanner.close();
    }
}
```

Prim's Algorithm

Prim's algorithm is another common and easy-to-write minimum spanning tree algorithm. The basic idea is to start from a single node and continuously add nodes (as opposed to Kruskal's algorithm which adds edges).

Implementation

Illustration:

Specifically, each time we select the node with the smallest distance and update the distances of other nodes with the new edge.

This is similar to Dijkstra's algorithm: each time we find the node with the smallest distance, either by brute force or using a heap.

Heap optimization is similar to Dijkstra's heap optimization. However, if using a binary heap or other heaps that do not support \(O(1)\) decrease-key, the complexity is not better than Kruskal's, and the constant factor is larger. Therefore, Kruskal's algorithm is generally used. On dense graphs, especially complete graphs, the brute-force Prim's complexity is better than Kruskal's, but it may not actually run faster.

Brute force: \(O(n^2+m)\).

Binary heap: \(O((n+m) \log n)\).

Fibonacci heap: \(O(n \log n + m)\).

Pseudocode:

\[ \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} \]

Note: The above code only computes the weight of the minimum spanning tree. To output the actual tree, you need to record which edge each node's \(dis\) represents.

Code Implementation 
 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's algorithm optimized with a binary heap.
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr 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] = true;
    ++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;
}

Proof

Start from any node, dividing nodes into two categories: added and not added.

Each time, among the unadded nodes, find the node with the minimum edge weight to any added node.

Then add this node and connect it with that minimum-weight edge.

Repeat \(n-1\) times.

Proof: Again, we show that at each step, there exists a minimum spanning tree containing the current edge set.

Base case: With only one node, it obviously holds.

Inductive step: If it holds at some step, with current edge set \(F\) belonging to MST \(T\), and we are about to add edge \(e\).

If \(e\) belongs to \(T\), then it holds.

Otherwise, consider another edge \(f\) on the cycle in \(T+e\) that can be added to the current edge set.

First, the weight of \(f\) cannot be less than that of \(e\); otherwise, \(f\) would have been chosen instead of \(e\).

Second, the weight of \(f\) cannot be greater than that of \(e\); otherwise, \(T+e-f\) would be a smaller spanning tree.

Thus, \(e\) and \(f\) have equal weights, and \(T+e-f\) is also a minimum spanning tree containing \(F\).

Borůvka's Algorithm

Next, we introduce another algorithm for solving the minimum spanning tree problem—Borůvka's algorithm. This algorithm combines ideas from the previous two algorithms. It can be used to find the minimum spanning forest of an undirected graph (for a connected undirected graph, it is the minimum spanning tree).

Borůvka's algorithm has advantages in problems where edges have special properties. For example, the complete graph problem in CF888G.

To describe the algorithm, we need some definitions:

  1. Define \(E'\) as the edges of the current minimum spanning forest. During the algorithm, we gradually add edges to \(E'\). Define a connected component as a vertex set \(V'\subseteq V\) such that any two vertices \(u\), \(v\) in this set are connected (mutually reachable) in the subgraph formed by the edges in \(E'\).
  2. Define the minimum edge of a connected component as the edge with the smallest weight connecting it to another component.

Initially, \(E'=\varnothing\), and each vertex is its own connected component:

  1. Compute which connected component each vertex belongs to. Set each component to have "no minimum edge".
  2. Traverse each edge \((u, v)\). If \(u\) and \(v\) are in different components, use this edge's weight to update the minimum edge of the components containing \(u\) and \(v\).
  3. If all components have no minimum edge, exit. At this point, \(E'\) is the edge set of the minimum spanning forest. Otherwise, add the minimum edge of each component that has one to \(E'\), and return to step 1.

The following animation illustrates an example (image from Wikipedia):

eg

When the original graph is connected, the number of components at least halves each iteration, so the algorithm iterates at most \(O(\log V)\) times. For disconnected graphs, it is equivalent to multiple subproblems. Thus, the algorithm complexity is \(O(E\log V)\). Pseudocode (modified from Wikipedia):

\[ \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} \]

Note: Edge comparisons often require a secondary key (e.g., sorting by edge ID) to break ties when edge weights are equal.

Exercises

Uniqueness of Minimum Spanning Tree

Consider the uniqueness of the minimum spanning tree. If an edge is not in the edge set of the minimum spanning tree and can replace another edge with the same weight that is in the edge set of the minimum spanning tree, then the minimum spanning tree is not unique.

For Kruskal's algorithm, we can compute how many edges of the current weight can be added and how many are actually added. If these two numbers differ, it means these edges form a cycle with previous edges (this cycle contains at least two edges of the current weight; otherwise, based on the disjoint set union, this edge could not be added), indicating the minimum spanning tree is not unique.

To find edges with the same weight as the current edge, we only need to record head and tail pointers and use a monotonic queue to solve this problem efficiently in \(O(\alpha(m))\) time (where \(m\) is the number of edges), essentially the same as the original algorithm.

Example: 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
59
60
61
62
#include <algorithm>
#include <iostream>

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]); }

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z;
    std::sort(a + 1, a + m + 1, cmp);  // Sort first
    int num = 0, ans = 0, tail = 0, sum1 = 0, sum2 = 0;
    bool flag = true;
    for (int i = 1; i <= m + 1; i++) {  // Then use union-find to add edges
      if (i > tail) {
        if (sum1 != sum2) {
          flag = false;
          break;
        }
        sum1 = 0;
        for (int j = i; j <= m + 1; j++) {
          if (j > m || 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)
      cout << ans << '\n';
    else
      cout << "Not Unique!\n";
  }
  return 0;
}

Second Minimum Spanning Tree

Non-strict Second Minimum Spanning Tree

Definition

In an undirected graph, the spanning tree with the smallest sum of edge weights that is greater than or equal to the sum of the minimum spanning tree's edge weights.

Solution Method

  • Find the minimum spanning tree \(T\) of the undirected graph, and let its weight sum be \(M\).
  • For each unselected edge \(e = (u,v,w)\), find the edge with the maximum weight \(e' = (s,t,w')\) on the path from \(u\) to \(v\) in \(T\). Then replace \(e'\) with \(e\) in \(T\) to obtain a spanning tree \(T'\) with weight sum \(M' = M + w - w'\).
  • Take the minimum among all such \(M'\).

How to find the maximum edge weight on the path between \(u\) and \(v\)?

We can use binary lifting to maintain this. Preprocess each node's \(2^i\)-th ancestor and the maximum edge weight on the path to that ancestor. Then, during binary lifting for LCA, we can directly obtain the maximum edge weight.

Strict Second Minimum Spanning Tree

Definition

In an undirected graph, the spanning tree with the smallest sum of edge weights that is strictly greater than the sum of the minimum spanning tree's edge weights.

Solution Method

Consider the solution process for the non-strict second minimum spanning tree. Why is the obtained solution non-strict?

Because the minimum spanning tree ensures that the maximum edge weight on the path between \(u\) and \(v\) in the tree is no greater than the maximum edge weight on any other path from \(u\) to \(v\). In other words, when the weight of the edge used for replacement equals the weight of the replaced edge in the original spanning tree, the resulting second minimum spanning tree is non-strict.

The solution is natural: while maintaining the maximum edge weight on the path to the \(2^i\)-th ancestor, also maintain the strict second maximum edge weight. When the weight of the replacement edge equals the maximum edge weight on the path in the original tree, use the strict second maximum value for replacement.

This process can be solved using binary lifting with complexity \(O(m \log m)\).

Code Implementation 
  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
#include <algorithm>
#include <iostream>

constexpr int INF = 0x3fffffff;
constexpr 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];
  // Maximum edge weight on the path to ancestor
  int maxx[100010][22];
  // Second maximum edge weight on the path to ancestor, or -INF if none
  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]};
      // Get the maximum from these four values
      std::sort(kk, kk + 4);
      maxx[now][i] = kk[3];
      // Get the strict second maximum
      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] = true;
    }
    if (tot == n - 1) break;
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  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);
      // Find the maximum edge weight on the path not equal to 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);
      // Such an edge may not exist; update answer only if it exists
      if (std::max(tmpa, tmpb) > -INF)
        ans = std::min(ans, sum - std::max(tmpa, tmpb) + e[i].val);
    }
  }
  // Output -1 if the second minimum spanning tree does not exist
  std::cout << (ans == INF64 ? -1 : ans) << '\n';
  return 0;
}

Bottleneck Spanning Tree

Definition

A bottleneck spanning tree of an undirected graph \(G\) is a spanning tree whose maximum edge weight is the smallest among all spanning trees of \(G\).

Properties

A minimum spanning tree is a bottleneck spanning tree, but the converse is not necessarily true. That is, a minimum spanning tree is always a bottleneck spanning tree, but a bottleneck spanning tree may not be a minimum spanning tree.

To prove that a minimum spanning tree is always a bottleneck spanning tree, we can use contradiction: Let the maximum edge weight in the minimum spanning tree be \(w\). If the minimum spanning tree is not a bottleneck spanning tree, then all edge weights in the bottleneck spanning tree are less than \(w\). Remove the longest edge from the original minimum spanning tree and connect the two resulting trees with an edge from the bottleneck spanning tree. The new spanning tree will have a smaller total weight than the original minimum spanning tree, leading to a contradiction.

Example

POJ 2395 Out of Hay

Given n farms and m edges, farms numbered 1 to n, a person needs to travel from farm 1 to other farms. Find the maximum amount of water he needs to carry during the journey. Note that he can replenish water at each farm, and the total path length should be minimized. The problem asks for the maximum edge weight in the bottleneck tree, which can be solved by finding the minimum spanning tree.

Minimum Bottleneck Path

Definition

A minimum bottleneck path from x to y in an undirected graph \(G\) is a simple path such that the maximum edge weight on this path is the smallest among all simple paths from x to y.

Properties

By the definition of the minimum spanning tree, the maximum edge weight on the minimum bottleneck path from x to y equals the maximum edge weight on the path from x to y in the minimum spanning tree. Although the minimum spanning tree is not unique, the maximum edge weight on the path from x to y is the same for all minimum spanning trees and is the minimum possible. That is, the path from x to y in any minimum spanning tree is a minimum bottleneck path.

However, not all minimum bottleneck paths exist as a simple path from x to y in some minimum spanning tree.

For example, consider the following graph:

The minimum bottleneck paths from 1 to 4 are clearly: 1-2-3-4 and 1-3-4.

But 1-2 does not appear in any minimum spanning tree.

Applications

Since minimum bottleneck paths are not unique, we typically ask for the maximum edge weight on a minimum bottleneck path.

That is, we need to find the max on a chain in the minimum spanning tree.

Binary lifting or heavy-light decomposition can solve this; we will not elaborate here.

Kruskal Reconstruction Tree

Definition

While running Kruskal's algorithm, we add edges in increasing order. We follow this order.

First, create \(n\) sets, each containing exactly one node with weight \(0\).

Each time we add an edge merging two sets, we create a new node with weight equal to the added edge's weight. Set the roots of the two sets as the left and right children of this new node. Then merge the two sets and the new node into one set, with the new node as the root.

After \(n-1\) rounds, we obtain a binary tree with exactly \(n\) leaves, and each non-leaf node has exactly two children. This tree is called the Kruskal reconstruction tree.

For example:

The Kruskal reconstruction tree for this graph is:

Properties

It is not hard to see that the minimum of the maximum edge weights over all simple paths between two points in the original graph = the maximum edge weight on the simple path between the two points in the minimum spanning tree = the weight of the LCA of the two points in the Kruskal reconstruction tree.

That is, all points \(y\) such that the minimum of the maximum edge weights on simple paths to \(x\) is \(\leq val\) are exactly the leaves of a certain subtree in the Kruskal reconstruction tree, and that subtree contains all such points.

We find the shallowest node on the path from \(x\) to the root in the Kruskal reconstruction tree with weight \(\leq val\). This is precisely the root of the subtree containing all such points.

If we need the maximum of the minimum edge weights over all simple paths between two points in the original graph, run Kruskal's algorithm adding edges in decreasing order of weight.

「LOJ 137」Minimum Bottleneck Path (Enhanced) 
  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
#include <algorithm>
#include <iostream>

using namespace std;

constexpr 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() {  // Minimum Spanning Tree
  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();  // Preprocessing
  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 Return

First, precompute the shortest path from each node to the root.

Construct the maximum spanning tree based on altitude. Clearly, the nodes reachable in each query are those on the path from the query point in the maximum spanning tree with minimum edge weight \(> p\).

By the properties of the Kruskal reconstruction tree, these nodes are all in a single subtree and are exactly its leaves.

That is, we only need to compute the minimum weight among leaves in each subtree of the Kruskal reconstruction tree to support subtree queries.

The root node for the query can be found using binary lifting on the Kruskal reconstruction tree.

Time complexity: \(O((n+m+Q) \log n)\).

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用