Bỏ qua

Cây khung nhỏ nhất (MST)

Định nghĩa

Trước khi đọc phần này, bạn nên đọc Các khái niệm cơ bản về đồ thị và Cây cơ bản, đồng thời nắm được các định nghĩa sau:

  1. Đồ thị con sinh (subgraph)
  2. Cây khung (spanning tree)

Ta định nghĩa Cây khung nhỏ nhất (Minimum Spanning Tree, MST) của một đồ thị vô hướng liên thông là cây khung có tổng trọng số các cạnh nhỏ nhất.

Lưu ý: Chỉ đồ thị liên thông mới có cây khung, còn với đồ thị không liên thông thì chỉ tồn tại rừng khung (spanning forest).

Thuật toán Kruskal

Thuật toán Kruskal là một trong những thuật toán tìm cây khung nhỏ nhất phổ biến và dễ cài đặt, do Kruskal phát minh. Ý tưởng cơ bản là thêm các cạnh theo thứ tự tăng dần trọng số, đây là một thuật toán tham lam (greedy).

Kiến thức nền tảng

DSU - Hợp nhất tập hợp (Union-Find), Tham lam (Greedy), Lưu trữ đồ thị.

Cài đặt

Minh họa:

Giả mã:

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{Các cạnh của đồ thị } e , \text{ mỗi phần tử } (u, v, w) \\ & \text{ nghĩa là có cạnh nối } u \text{ và } v \text{ với trọng số } w . \\ 2 & \textbf{Output. } \text{Các cạnh của cây khung nhỏ nhất của đồ thị đầu vào}.\\ 3 & \textbf{Phương pháp. } \\ 4 & result \gets \varnothing \\ 5 & \text{Sắp xếp } e \text{ theo thứ tự không giảm của trọng số } w \\ 6 & \textbf{for} \text{ mỗi } (u, v, w) \text{ trong } e \text{ đã sắp xếp} \\ 7 & \qquad \textbf{if } u \text{ và } v \text{ chưa cùng tập hợp trong DSU } \\ 8 & \qquad\qquad \text{Hợp nhất } u \text{ và } v \text{ trong DSU} \\ 9 & \qquad\qquad result \gets result\;\bigcup\ \{(u, v, w)\} \\ 10 & \textbf{return } result \end{array} \]

Thuật toán đơn giản nhưng cần cấu trúc dữ liệu phù hợp... Cụ thể, cần duy trì một rừng, kiểm tra hai đỉnh có cùng cây không, và hợp nhất hai cây.

Trừu tượng hơn, cần duy trì nhiều tập hợp, kiểm tra hai phần tử có cùng tập hợp không, và hợp nhất hai tập hợp.

Việc kiểm tra hai đỉnh liên thông và hợp nhất hai đỉnh có thể dùng DSU (Disjoint Set Union).

Nếu dùng thuật toán sắp xếp \(O(m\log m)\) và DSU \(O(m\alpha(m, n))\) hoặc \(O(m\log n)\), ta đạt độ phức tạp \(O(m\log m)\) cho Kruskal.

Chứng minh

Ý tưởng đơn giản: Để xây dựng cây khung nhỏ nhất, ta bắt đầu từ cạnh nhỏ nhất, thêm dần các cạnh theo thứ tự tăng dần trọng số, nếu thêm cạnh tạo thành chu trình thì bỏ qua, cho đến khi có đủ \(n-1\) cạnh.

Chứng minh: Dùng quy nạp, chứng minh tại mọi thời điểm, tập cạnh mà Kruskal chọn đều nằm trong một cây khung nhỏ nhất nào đó.

Cơ sở: Ban đầu, rõ ràng đúng (cây khung nhỏ nhất tồn tại).

Bước quy nạp: Giả sử đúng tại thời điểm hiện tại, tập cạnh là \(F\), \(T\) là một cây khung nhỏ nhất chứa \(F\), xét cạnh tiếp theo \(e\).

Nếu \(e\) thuộc \(T\), hiển nhiên đúng.

Nếu không, \(T+e\) tạo thành một chu trình, xét cạnh \(f\) trên chu trình này không thuộc \(F\) (tồn tại ít nhất một cạnh như vậy).

Trọng số \(f\) không nhỏ hơn \(e\), nếu nhỏ hơn thì \(f\) đã được chọn trước \(e\).

Trọng số \(f\) cũng không lớn hơn \(e\), nếu lớn hơn thì \(T+e-f\) là cây khung tốt hơn \(T\) (mâu thuẫn).

Vậy \(T+e-f\) vẫn là cây khung nhỏ nhất chứa \(F\), quy nạp thành công.

Bài mẫu

洛谷 P1195 Bầu trời trong túi

Có \(n\) đám mây, bạn cần nối chúng thành \(k\) viên kẹo bông, nối đám mây \(X_i\) và \(Y_i\) tốn \(L_i\), hỏi tổng chi phí nhỏ nhất.

Code mẫu 
 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];  // 定义父亲
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;
}

// 标准并查集
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 算法
void kruskal() {
  int tot = 0;  // 存已选了的边数
  int ans = 0;  // 存总的代价
  for (int i = 1; i <= m; i++) {
    int xr = findroot(g[i].u), yr = findroot(g[i].v);
    if (xr != yr) {        // 如果父亲不一样
      Merge(xr, yr);       // 合并
      tot++;               // 边数增加
      ans += g[i].w;       // 代价增加
      if (tot == n - k) {  // 检查选的边数是否满足 k 个棉花糖
        cout << ans << '\n';
        return;
      }
    }
  }
  cout << "No Answer\n";  // 无法连成
}

int main() {
  cin >> n >> m >> k;
  if (n == k) {  // 特判边界情况
    cout << "0\n";
    return 0;
  }
  for (int i = 1; i <= n; i++) {  // 初始化
    fa[i] = i;
  }
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);  // 添加边
  }
  sort(g + 1, g + m + 1, cmp);  // 先按边权排序
  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  # 定义父亲
g = []


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


# 标准并查集
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 算法
def kruskal():
    tot = 0  # 存已选了的边数
    ans = 0  # 存总的代价
    for e in g:
        x = findroot(e.u)
        y = findroot(e.v)
        if x != y:  # 如果父亲不一样
            fa[x] = y  # 合并
            tot += 1  # 边数增加
            ans += e.w  # 代价增加
            if tot == n - k:  # 检查选的边数是否满足 k 个棉花糖
                print(ans)
                return
    print("No Answer")  # 无法连成


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    if n == k:  # 特判边界情况
        print("0")
        exit()
    for i in range(1, n + 1):  # 初始化
        fa[i] = i
    for i in range(1, m + 1):
        u, v, w = map(int, input().split())
        add(u, v, w)  # 添加边
    g.sort(key=lambda edge: edge.w)  # 先按边权排序
    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
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];  // 定义父亲
    static int m, n, k;  // n 表示点的数量， m 表示边的数量，k 表示需要的棉花糖个数

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

    // 标准并查集
    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 算法
    static void kruskal() {
        int tot = 0;  // 存已选了的边数
        int ans = 0;  // 存总的代价

        for (int i = 1; i <= m; i++) {
            int xr = findroot(edges[i].u);
            int yr = findroot(edges[i].v);
            if (xr != yr) {   // 如果父亲不一样
                Merge(xr, yr); // 合并
                tot++; // 边数增加
                ans += edges[i].w; // 代价增加
                if (tot == n - k) {  // 检查选的边数是否满足 k 个棉花糖
                    System.out.println(ans);
                    return;
                }
            }
        }
        System.out.println("No Answer");  // 无法连成
    }

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

        if (n == k) { // 特判边界情况
            System.out.println("0");
            return;
        }

        // 初始化
        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);  // 添加边
        }
        Arrays.sort(edges, 1, m + 1, (a, b) -> Integer.compare(a.w, b.w));  // 先按边权排序
        kruskal();
        scanner.close();
    }
}

Thuật toán Prim

Thuật toán Prim là một thuật toán phổ biến khác để tìm cây khung nhỏ nhất. Ý tưởng là bắt đầu từ một đỉnh, liên tục thêm đỉnh mới (khác với Kruskal là thêm cạnh).

Cài đặt

Minh họa:

Cụ thể, mỗi lần chọn đỉnh có khoảng cách nhỏ nhất tới tập đã chọn, và dùng các cạnh mới cập nhật khoảng cách các đỉnh còn lại.

Thực chất giống thuật toán Dijkstra: mỗi lần chọn đỉnh có khoảng cách nhỏ nhất, có thể tìm bằng vét cạn hoặc dùng heap.

Nếu dùng heap nhị phân (không hỗ trợ decrease-key \(O(1)\)), độ phức tạp không tốt hơn Kruskal, và hằng số cũng lớn hơn. Thông thường, Kruskal được ưu tiên hơn, nhưng với đồ thị dày đặc (đặc biệt là đồ thị đầy đủ), Prim vét cạn có thể nhanh hơn Kruskal, nhưng không chắc chạy nhanh hơn thực tế.

Vét cạn: \(O(n^2+m)\).

Heap nhị phân: \(O((n+m) \log n)\).

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

Giả mã:

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{Các đỉnh của đồ thị }V\text{ ; hàm }g(u, v)\text{ là trọng số cạnh }(u, v)\text{;}\\ & \text{hàm }adj(v)\text{ là tập đỉnh kề với }v.\\ 2 & \textbf{Output. } \text{Tổng trọng số cây khung nhỏ nhất của đồ thị.} \\ 3 & \textbf{Phương pháp.} \\ 4 & result \gets 0 \\ 5 & \text{Chọn một đỉnh bất kỳ làm }root \\ 6 & dis(root)\gets 0 \\ 7 & \textbf{for } \text{mỗi đỉnh }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{đỉnh có }dis\text{ nhỏ nhất trong }rest \\ 12 & \qquad result\gets result+dis(cur) \\ 13 & \qquad rest\gets rest-\{cur\} \\ 14 & \qquad \textbf{for}\text{ mỗi đỉnh }v\in adj(cur) \\ 15 & \qquad\qquad dis(v)\gets\min(dis(v), g(cur, v)) \\ 16 & \textbf{return } result \end{array} \]

Lưu ý: Đoạn code trên chỉ tính tổng trọng số cây khung nhỏ nhất, nếu muốn in ra phương án cần lưu lại cạnh ứng với mỗi \(dis\).

Code mẫu 
 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 tối ưu bằng heap nhị phân.
#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;
}

Chứng minh

Bắt đầu từ một đỉnh bất kỳ, chia các đỉnh thành hai loại: đã chọn và chưa chọn.

Mỗi lần chọn đỉnh chưa chọn có cạnh nối với tập đã chọn có trọng số nhỏ nhất.

Sau đó thêm đỉnh này vào, nối bằng cạnh nhỏ nhất.

Lặp lại \(n-1\) lần.

Chứng minh: Tại mỗi bước, luôn tồn tại một cây khung nhỏ nhất chứa tập cạnh đã chọn.

Cơ sở: Khi chỉ có một đỉnh, hiển nhiên đúng.

Bước quy nạp: Nếu đúng ở bước hiện tại, tập cạnh là \(F\), thuộc cây khung nhỏ nhất \(T\), xét cạnh \(e\) sắp thêm.

Nếu \(e\) thuộc \(T\), hiển nhiên đúng.

Nếu không, xét chu trình \(T+e\) và cạnh \(f\) khác có thể thay thế.

Trọng số \(f\) không nhỏ hơn \(e\), nếu nhỏ hơn thì đã chọn \(f\) trước.

Trọng số \(f\) cũng không lớn hơn \(e\), nếu lớn hơn thì \(T+e-f\) là cây khung tốt hơn \(T\).

Vậy \(e\) và \(f\) bằng nhau, \(T+e-f\) vẫn là cây khung nhỏ nhất chứa \(F\).

Thuật toán Boruvka

Tiếp theo là một thuật toán khác để tìm cây khung nhỏ nhất: Boruvka. Ý tưởng là kết hợp hai thuật toán trên. Boruvka có thể dùng để tìm rừng khung nhỏ nhất cho đồ thị vô hướng (đồ thị liên thông thì là cây khung nhỏ nhất).

Với các bài toán có tính chất đặc biệt về cạnh, Boruvka có ưu thế, ví dụ bài CF888G với đồ thị đầy đủ.

Một số định nghĩa:

  1. Gọi \(E'\) là tập cạnh của rừng khung nhỏ nhất hiện tại. Trong quá trình thuật toán, ta dần thêm cạnh vào \(E'\). Khối liên thông là tập đỉnh \(V'\subseteq V\) sao cho mọi cặp \(u,v\) trong \(V'\) liên thông qua các cạnh trong \(E'\).
  2. Cạnh nhỏ nhất của một khối liên thông là cạnh nối khối đó với khối khác có trọng số nhỏ nhất.

Ban đầu, \(E'=\varnothing\), mỗi đỉnh là một khối liên thông riêng:

  1. Xác định mỗi đỉnh thuộc khối liên thông nào. Đặt mỗi khối là "chưa có cạnh nhỏ nhất".
  2. Duyệt từng cạnh \((u, v)\), nếu \(u\) và \(v\) khác khối, dùng cạnh này cập nhật cạnh nhỏ nhất của hai khối.
  3. Nếu mọi khối đều "chưa có cạnh nhỏ nhất", dừng thuật toán, \(E'\) là rừng khung nhỏ nhất. Ngược lại, thêm các cạnh nhỏ nhất của từng khối vào \(E'\), quay lại bước 1.

Minh họa động (nguồn: Wikipedia):

eg

Nếu đồ thị liên thông, mỗi vòng lặp số khối liên thông giảm ít nhất một nửa, nên thuật toán lặp tối đa \(O(\log V)\) lần. Nếu không liên thông thì là nhiều bài toán con. Độ phức tạp \(O(E\log V)\). Giả mã (chỉnh sửa từ Wikipedia):

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{Đồ thị }G\text{ với các cạnh có trọng số phân biệt. } \\ 2 & \textbf{Output. } \text{Rừng khung nhỏ nhất của }G . \\ 3 & \textbf{Phương pháp. } \\ 4 & \text{Khởi tạo rừng }F\text{ gồm các cây một đỉnh} \\ 5 & \textbf{while } \text{True} \\ 6 & \qquad \text{Tìm các thành phần liên thông của }F\text{ và gán nhãn cho mỗi đỉnh của }G \\ 7 & \qquad \text{Khởi tạo cạnh rẻ nhất cho mỗi thành phần là "None"} \\ 8 & \qquad \textbf{for } \text{mỗi cạnh }(u, v)\text{ của }G \\ 9 & \qquad\qquad \textbf{if } u\text{ và }v\text{ khác thành phần} \\ 10 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ rẻ hơn cạnh rẻ nhất của thành phần }u \\ 11 & \qquad\qquad\qquad\qquad\text{ Gán }(u, v)\text{ là cạnh rẻ nhất của thành phần }u \\ 12 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ rẻ hơn cạnh rẻ nhất của thành phần }v \\ 13 & \qquad\qquad\qquad\qquad\text{ Gán }(u, v)\text{ là cạnh rẻ nhất của thành phần }v \\ 14 & \qquad \textbf{if }\text{ mọi thành phần đều không có cạnh rẻ nhất} \\ 15 & \qquad\qquad \textbf{return } F \\ 16 & \qquad \textbf{for }\text{ mỗi thành phần có cạnh rẻ nhất} \\ 17 & \qquad\qquad\text{ Thêm cạnh rẻ nhất vào }F \\ \end{array} \]

Lưu ý: Khi so sánh cạnh, nên dùng thêm tiêu chí phụ (ví dụ chỉ số cạnh) để phân biệt khi trọng số bằng nhau.

Bài tập

Tính duy nhất của cây khung nhỏ nhất

Xét tính duy nhất của cây khung nhỏ nhất. Nếu một cạnh không thuộc cây khung nhỏ nhất, nhưng có thể thay thế cho một cạnh cùng trọng số, thuộc cây khung nhỏ nhất, thì cây khung nhỏ nhất là không duy nhất.

Với Kruskal, chỉ cần đếm số cạnh cùng trọng số có thể chọn và số cạnh thực sự được chọn. Nếu hai số này khác nhau, tức là các cạnh này cùng tạo thành một chu trình (trong chu trình có ít nhất hai cạnh cùng trọng số), tức là cây khung nhỏ nhất không duy nhất.

Để tìm các cạnh cùng trọng số, chỉ cần lưu lại chỉ số đầu/cuối, dùng hàng đợi đơn điệu là có thể giải quyết trong \(O(\alpha(m))\) (với \(m\) là số cạnh), gần như không tăng độ phức tạp so với thuật toán gốc.

Bài mẫu: 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);  // 先排序
    int num = 0, ans = 0, tail = 0, sum1 = 0, sum2 = 0;
    bool flag = true;
    for (int i = 1; i <= m + 1; i++) {  // 再并查集加边
      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;
}

Cây khung nhỏ thứ hai

Cây khung nhỏ thứ hai không chặt (non-strict)

Định nghĩa

Trong đồ thị vô hướng, cây khung có tổng trọng số nhỏ nhất lớn hơn hoặc bằng cây khung nhỏ nhất.

Cách tìm

  • Tìm cây khung nhỏ nhất \(T\), tổng trọng số \(M\).
  • Duyệt từng cạnh chưa chọn \(e = (u,v,w)\), tìm trên \(T\) cạnh lớn nhất trên đường từ \(u\) đến \(v\) là \(e' = (s,t,w')\), thay \(e'\) bằng \(e\) được cây khung mới \(T'\) có tổng trọng số \(M' = M + w - w'\).
  • Lấy giá trị nhỏ nhất trong các \(M'\).

Làm sao tìm cạnh lớn nhất trên đường \(u,v\)? Dùng kỹ thuật "bậc thang" (binary lifting), tiền xử lý tổ tiên \(2^i\) của mỗi đỉnh và trọng số lớn nhất trên đường đó, khi tìm LCA thì truy vấn luôn được.

Cây khung nhỏ thứ hai chặt (strict)

Định nghĩa

Trong đồ thị vô hướng, cây khung có tổng trọng số nhỏ nhất lớn hơn cây khung nhỏ nhất.

Cách tìm

Ở cách trên, vì cây khung nhỏ nhất đảm bảo cạnh lớn nhất trên đường \(u\) đến \(v\) không lớn hơn các đường khác, nên nếu cạnh thay thế có trọng số bằng cạnh bị thay, kết quả là cây khung nhỏ thứ hai không chặt.

Cách giải quyết: Khi tiền xử lý tổ tiên \(2^i\), ngoài trọng số lớn nhất còn lưu trọng số lớn thứ hai (nếu có). Khi thay thế, nếu trọng số cạnh thay bằng trọng số lớn nhất, thì dùng trọng số lớn thứ hai.

Có thể dùng binary lifting, độ phức tạp \(O(m \log m)\).

Code mẫu 
  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];
  // 到祖先的路径上边权最大的边
  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] = 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);
      // 找到路径上不等于 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;
}

Cây khung nút thắt (Bottleneck Spanning Tree)

Định nghĩa

Cây khung nút thắt của đồ thị vô hướng \(G\) là cây khung mà trọng số cạnh lớn nhất là nhỏ nhất trong tất cả các cây khung của \(G\).

Tính chất

Cây khung nhỏ nhất luôn là cây khung nút thắt, nhưng ngược lại thì không chắc. Có thể chứng minh bằng phản chứng: Nếu cây khung nhỏ nhất có cạnh lớn nhất là \(w\), giả sử tồn tại cây khung nút thắt mà mọi cạnh đều nhỏ hơn \(w\), thì thay cạnh lớn nhất của cây khung nhỏ nhất bằng một cạnh trong cây khung nút thắt sẽ được cây khung có tổng trọng số nhỏ hơn, mâu thuẫn.

Bài mẫu

POJ 2395 Out of Hay

Cho \(n\) trang trại và \(m\) cạnh, các trang trại đánh số \(1\) đến \(n\). Một người xuất phát từ trang trại \(1\) đến các trang trại khác, hỏi trên đường đi anh ta cần mang nhiều nhất bao nhiêu nước (mỗi lần đến trang trại có thể tiếp nước, tổng đường đi phải nhỏ nhất). Bài này yêu cầu cạnh lớn nhất trên cây khung nhỏ nhất.

Đường đi nút thắt nhỏ nhất (Minimum Bottleneck Path)

Định nghĩa

Trong đồ thị vô hướng \(G\), đường đi nút thắt nhỏ nhất từ \(x\) đến \(y\) là đường đi đơn giản mà cạnh lớn nhất trên đường đi là nhỏ nhất trong tất cả các đường đi từ \(x\) đến \(y\).

Tính chất

Theo định nghĩa cây khung nhỏ nhất, cạnh lớn nhất trên đường đi từ \(x\) đến \(y\) trên cây khung nhỏ nhất chính là giá trị nhỏ nhất có thể. Dù cây khung nhỏ nhất không duy nhất, nhưng trên mọi cây khung nhỏ nhất, giá trị này đều như nhau.

Tuy nhiên, không phải mọi đường đi nút thắt nhỏ nhất đều là đường đi trên cây khung nhỏ nhất.

Ví dụ:

Đường đi nút thắt nhỏ nhất từ \(1\) đến \(4\) có hai đường: 1-2-3-4 và 1-3-4.

Nhưng cạnh 1-2 không xuất hiện trong bất kỳ cây khung nhỏ nhất nào.

Ứng dụng

Vì đường đi nút thắt nhỏ nhất không duy nhất, thường chỉ hỏi giá trị cạnh lớn nhất trên đường đi đó.

Tức là, cần truy vấn max trên đường đi trong cây khung nhỏ nhất.

Có thể dùng binary lifting, HLD,... để giải quyết.

Cây tái cấu trúc Kruskal

Định nghĩa

Trong quá trình chạy Kruskal, ta thêm các cạnh theo thứ tự tăng dần trọng số.

Ban đầu tạo \(n\) tập hợp, mỗi tập có một đỉnh, trọng số \(0\).

Mỗi lần thêm cạnh, hợp nhất hai tập hợp, tạo một đỉnh mới có trọng số bằng trọng số cạnh vừa thêm, hai gốc của hai tập hợp làm con trái/phải của đỉnh mới. Sau đó hợp nhất hai tập và đỉnh mới thành một tập, đỉnh mới là gốc.

Sau \(n-1\) lần, ta được một cây nhị phân có đúng \(n\) lá, mỗi nút trong có hai con. Đó là cây tái cấu trúc Kruskal.

Ví dụ:

Cây tái cấu trúc Kruskal của đồ thị trên:

Tính chất

Dễ thấy, giá trị nhỏ nhất của cạnh lớn nhất trên mọi đường đi đơn giản giữa hai đỉnh \(x, y\) trong đồ thị gốc = max cạnh trên đường đi giữa \(x, y\) trên cây khung nhỏ nhất = giá trị tại LCA của \(x, y\) trên cây tái cấu trúc Kruskal.

Tức là, tập các đỉnh \(y\) sao cho max cạnh trên đường từ \(x\) đến \(y\) không vượt quá \(val\) chính là tập lá của một cây con trên cây tái cấu trúc Kruskal.

Để tìm tập này, chỉ cần tìm trên cây tái cấu trúc Kruskal đỉnh tổ tiên nông nhất trên đường từ \(x\) lên gốc có trọng số \(\leq val\).

Nếu muốn tìm min cạnh lớn nhất trên mọi đường đi đơn giản giữa hai đỉnh, thì chạy Kruskal theo thứ tự giảm dần trọng số.

「LOJ 137」Đường đi nút thắt nhỏ nhất - bản mở rộng 
  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() {  // 最小生成树
  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 Quy trình trở về

Đầu tiên tiền xử lý đường đi ngắn nhất từ mỗi đỉnh đến gốc.

Xây dựng cây khung lớn nhất theo độ cao. Rõ ràng, mỗi truy vấn tìm các đỉnh có thể đến được là các đỉnh trên đường đi từ đỉnh truy vấn đến gốc trên cây khung lớn nhất có trọng số cạnh nhỏ nhất \(> p\).

Theo tính chất cây tái cấu trúc Kruskal, các đỉnh này là tập lá của một cây con.

Chỉ cần truy vấn min trọng số lá trong cây con đó.

Có thể tìm gốc cây con bằng binary lifting trên cây tái cấu trúc Kruskal.

Độ phức tạp \(O((n+m+Q) \log n)\).

````

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page: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, toprise
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply