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

Cây khung nhỏ nhất (Minimum Spanning Tree, MST) là tập $n-1$ cạnh nối tất cả $n$ đỉnh của một đồ thị vô hướng có trọng số sao cho tổng trọng số nhỏ nhất. Thử mọi cây khung là bất khả thi (đồ thị đầy đủ $n$ đỉnh có $n^{n-2}$ cây khung), nhưng nhờ hai tính chất tham lam đơn giản, thuật toán Kruskal giải trong $O(m\log m)$ và Prim trong $O(m\log n)$ (hoặc $O(n^2)$ cho đồ thị dày). MST còn là chìa khóa cho cả một họ bài "đường đi có cạnh lớn nhất nhỏ nhất" (minimax), "cạnh nào có thể thuộc MST", "mạng lưới rẻ nhất"... rất hay gặp trong đề VOI.

Định nghĩa

Cho đồ thị vô hướng liên thông $G=(V,E)$, $|V|=n$, $|E|=m$, mỗi cạnh $e$ có trọng số $w(e)$.

• Cây khung (spanning tree): tập con $T\subseteq E$ gồm đúng $n-1$ cạnh, nối mọi đỉnh và không có chu trình.
• Cây khung nhỏ nhất: cây khung có $w(T)={\sum }_{e\in T}w(e)$ nhỏ nhất. Có thể có nhiều MST khác nhau (khi có cạnh bằng trọng số), nhưng tổng trọng số nhỏ nhất thì duy nhất.
• Nếu đồ thị không liên thông, không tồn tại cây khung; khi đó ta nói về rừng khung nhỏ nhất (mỗi thành phần một cây).

Ba sự thật về cây sẽ được dùng liên tục:

1. Thêm một cạnh bất kỳ vào cây khung tạo ra đúng một chu trình.
2. Xóa một cạnh bất kỳ khỏi cây khung chia cây thành đúng hai phần; đó là một lát cắt (cut) $(S,V⧵S)$.
3. Trong cây, giữa hai đỉnh có đúng một đường đi.

Ý tưởng / Trực giác: hai tính chất nền tảng

Mọi thuật toán MST đều là tham lam, và tính đúng của chúng dựa trên hai tính chất đối ngẫu dưới đây. Cả hai đều chứng minh bằng lập luận trao đổi (exchange argument): lấy một MST, đổi một cạnh lấy cạnh khác mà tổng không tăng.

Tính chất lát cắt (cut property)

Với mọi lát cắt $(S,V⧵S)$, gọi $e$ là cạnh nhẹ nhất trong các cạnh có một đầu thuộc $S$, một đầu thuộc $V⧵S$. Khi đó tồn tại một MST chứa $e$. Nếu $e$ nhẹ nhất hẳn (không có cạnh cắt nào bằng nó), thì mọi MST đều chứa $e$.

Chứng minh. Lấy MST $T$ bất kỳ không chứa $e=(u,v)$. Thêm $e$ vào $T$ tạo ra một chu trình. Chu trình này đi từ $u\in S$ sang $v\notin S$ bằng $e$ rồi phải quay về $S$, nên nó còn ít nhất một cạnh khác $f$ cắt lát cắt. Vì $e$ nhẹ nhất trong các cạnh cắt, $w(f)\ge w(e)$. Cây $T^{\prime }=T-f+e$ vẫn là cây khung và $w(T^{\prime })=w(T)-w(f)+w(e)\le w(T)$, nên $T^{\prime }$ cũng là MST và chứa $e$. Nếu $w(e)<w(f)$ hẳn thì $w(T^{\prime })<w(T)$, mâu thuẫn, nên mọi MST phải chứa $e$. $∎$

Dạng mạnh hơn (dùng cho thuật toán tham lam). Thuật toán không chỉ cần "có một MST chứa $e$", mà cần "có một MST chứa mọi cạnh đã chọn và cả $e$":

Nếu tập cạnh $A$ đã chọn nằm trong một MST $T$, và không cạnh nào của $A$ cắt lát cắt $(S,V⧵S)$, thì với $e$ là cạnh nhẹ nhất cắt lát cắt, $A\cup \{e\}$ cũng nằm trong một MST.

Chứng minh y hệt trên: cạnh $f$ bị bỏ ra khỏi $T$ cắt lát cắt nên $f\notin A$, do đó $T^{\prime }=T-f+e$ vẫn chứa toàn bộ $A$. Áp dụng lặp lại từ $A=\varnothing$, mỗi bước thêm một cạnh như vậy, cuối cùng ta được đúng một MST.

Tính chất chu trình (cycle property)

Với mọi chu trình $C$, nếu $e$ là cạnh nặng nhất hẳn trên $C$ thì $e$ không thuộc MST nào. (Nếu $e$ chỉ nặng nhất không hẳn, tức có cạnh khác cùng trọng số lớn nhất, thì luôn có một MST không chứa $e$.)

Chứng minh. Giả sử MST $T$ chứa $e$. Xóa $e$ khỏi $T$ chia cây thành hai phần. Phần còn lại $C-e$ của chu trình là một đường đi nối hai đầu của $e$, nên nó có một cạnh $f$ nối hai phần đó. $f$ nằm trên $C$ nên $w(f)<w(e)$. Khi đó $T-e+f$ là cây khung nhẹ hơn $T$, mâu thuẫn. $∎$

Hai thuật toán từ hai góc nhìn

• Kruskal duyệt cạnh theo trọng số tăng dần; cạnh nào nối hai thành phần khác nhau thì lấy, cạnh nào tạo chu trình thì bỏ. Cạnh bị bỏ là cạnh nặng nhất trên chu trình nó tạo ra (các cạnh khác trên chu trình đều đã được xét trước nên không nặng hơn), nên bỏ nó là an toàn theo tính chất chu trình. Cạnh được lấy $e=(u,v)$ là cạnh nhẹ nhất cắt lát cắt "thành phần chứa $u$ | phần còn lại" (mọi cạnh nhẹ hơn đã được xét và nằm gọn trong các thành phần). Lát cắt này không cắt cạnh nào đã chọn (mọi cạnh đã chọn nằm gọn trong một thành phần), nên theo dạng mạnh của tính chất lát cắt, tập cạnh đã chọn cộng $e$ vẫn nằm trong một MST. Kiểm tra "cùng thành phần" dùng DSU.
• Prim mọc một cây từ một đỉnh gốc. Ở mỗi bước, lát cắt là (tập đỉnh đã vào cây $S$, phần còn lại), và Prim lấy cạnh nhẹ nhất cắt lát cắt đó. Mọi cạnh đã chọn đều có hai đầu trong $S$, nên lát cắt này không cắt cạnh nào đã chọn, và dạng mạnh của tính chất lát cắt đảm bảo cây đang mọc luôn nằm trong một MST. Việc tìm cạnh nhẹ nhất dùng heap (giống Dijkstra, nhưng khóa là trọng số cạnh chứ không phải khoảng cách cộng dồn).

Ví dụ chạy tay

Đồ thị 5 đỉnh, 7 cạnh:

   (1)-----4-----(2)
    |           / |
    1         3   2
    |       /     |
   (3)-----5-----(4)
      \         /
       6       7
        \     /
          (5)

cạnh: 1-3:1  2-4:2  2-3:3  1-2:4  3-4:5  3-5:6  4-5:7

Kruskal

Sắp cạnh tăng dần, duyệt lần lượt. Cột "thành phần" là trạng thái DSU sau khi xét cạnh.

cạnh    w   find(u) vs find(v)   quyết định    thành phần
1-3     1   khác                 LẤY           {1,3} {2} {4} {5}
2-4     2   khác                 LẤY           {1,3} {2,4} {5}
2-3     3   khác                 LẤY           {1,2,3,4} {5}
1-2     4   CÙNG (1-3-2)         bỏ            chu trình 1-2-3: cạnh 4 nặng nhất
3-4     5   CÙNG (3-2-4)         bỏ            chu trình 3-4-2: cạnh 5 nặng nhất
3-5     6   khác                 LẤY           {1,2,3,4,5}  -> đủ n-1 = 4 cạnh, dừng
4-5     7   (không cần xét)

MST = {1-3, 2-4, 2-3, 3-5}, tổng = 1 + 2 + 3 + 6 = 12

   (1)           (2)
    |           / |
    1         3   2
    |       /     |
   (3)           (4)
      \
       6
        \
          (5)

Prim (xuất phát từ đỉnh 1)

key[v] là trọng số cạnh nhẹ nhất đã biết nối $v$ vào cây hiện tại; mỗi bước lấy đỉnh ngoài cây có key nhỏ nhất.

bước  lấy đỉnh (key)   cập nhật key các đỉnh kề ngoài cây      key[1..5]
0     -                khởi tạo key[1] = 0                     0  ∞  ∞  ∞  ∞
1     1 (0)            2: 4, 3: 1                              .  4  1  ∞  ∞
2     3 (1)            2: min(4,3)=3, 4: 5, 5: 6               .  3  .  5  6
3     2 (3)            4: min(5,2)=2                           .  .  .  2  6
4     4 (2)            5: min(6,7)=6                           .  .  .  .  6
5     5 (6)            -                                       .  .  .  .  .

tổng = 0 + 1 + 3 + 2 + 6 = 12   (cùng cây với Kruskal)

Để ý bước 2: khi đỉnh 3 vào cây, key[2] giảm từ 4 xuống 3. Vì vậy ở bước 3, đỉnh 2 được kéo vào cây bằng cạnh 2-3 (trọng số 3) chứ không phải cạnh 1-2 (trọng số 4).

Cài đặt

Kruskal + DSU (C++)

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n + 1), sz(n + 1, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];  // path halving
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;           // already connected: edge would form a cycle
        if (sz[a] < sz[b]) swap(a, b);      // union by size
        parent[b] = a; sz[a] += sz[b];
        return true;
    }
};

struct Edge { int u, v; long long w; };

// Returns MST weight, or -1 if the graph is disconnected
long long kruskal(int n, vector<Edge> edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
    DSU dsu(n);
    long long total = 0;
    int taken = 0;
    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            if (++taken == n - 1) break;    // tree is complete
        }
    }
    return taken == n - 1 ? total : -1;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<Edge> edges(m);
    for (auto& e : edges) scanf("%d %d %lld", &e.u, &e.v, &e.w);
    printf("%lld\n", kruskal(n, edges));
}

Kruskal (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    edges = []
    for i in range(m):
        a, b, c = int(data[2 + 3*i]), int(data[3 + 3*i]), int(data[4 + 3*i])
        edges.append((c, a, b))
    edges.sort()

    parent = list(range(n + 1))
    size = [1] * (n + 1)

    def find(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:            # path compression, iterative
            parent[x], x = root, parent[x]
        return root

    total = taken = 0
    for c, a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            continue
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        total += c
        taken += 1
        if taken == n - 1:
            break
    print(total if taken == n - 1 else -1)

main()

Prim với heap (C++)

Phù hợp khi đồ thị cho sẵn danh sách kề. Đây là bản "lười" (lazy): một đỉnh có thể nằm trong heap nhiều lần, bản cũ bị bỏ qua khi lấy ra.

// adj[u] = list of (v, w); vertices 1..n
long long primHeap(int n, const vector<vector<pair<int, long long>>>& adj) {
    const long long INF = LLONG_MAX;
    vector<long long> key(n + 1, INF);
    vector<bool> inTree(n + 1, false);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    key[1] = 0;
    pq.push({0, 1});
    long long total = 0;
    int taken = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (inTree[u]) continue;            // stale entry
        inTree[u] = true;
        total += w;
        taken++;
        for (auto [v, c] : adj[u])
            if (!inTree[v] && c < key[v]) { // only push real improvements
                key[v] = c;
                pq.push({c, v});
            }
    }
    return taken == n ? total : -1;         // taken counts vertices, not edges
}

Prim $O(n^2)$ cho đồ thị dày

Khi đồ thị đầy đủ (ví dụ $n$ điểm trên mặt phẳng, cạnh giữa mọi cặp) thì $m\approx n^2/2$: sắp xếp $m$ cạnh cho Kruskal tốn cả bộ nhớ lẫn thời gian. Prim bản mảng không cần lưu cạnh, chỉ cần hàm tính trọng số, chạy $O(n^2)$ thời gian và $O(n)$ bộ nhớ.

// weight(i, j): cost of edge i-j (0-indexed), return LLONG_MAX if the edge is forbidden
template <class F>
long long primDense(int n, F weight) {
    const long long INF = LLONG_MAX;
    vector<long long> key(n, INF);
    vector<bool> inTree(n, false);
    key[0] = 0;
    long long total = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 0; v < n; v++)         // closest vertex outside the tree
            if (!inTree[v] && (u == -1 || key[v] < key[u])) u = v;
        if (key[u] == INF) return -1;       // remaining vertices unreachable
        inTree[u] = true;
        total += key[u];
        for (int v = 0; v < n; v++)
            if (!inTree[v]) key[v] = min(key[v], weight(u, v));
    }
    return total;
}

// Example: points (x[i], y[i]), cost = squared Euclidean distance
// long long ans = primDense(n, [&](int i, int j) {
//     long long dx = x[i] - x[j], dy = y[i] - y[j];
//     return dx * dx + dy * dy;
// });

Độ phức tạp

Lý giải:

• Kruskal: bước sắp xếp chiếm $O(m\log m)$. Sau đó mỗi cạnh gọi unite một lần, mỗi lần $O(\alpha (n))$ nhờ nén đường + gộp theo kích thước, tổng $O(m\alpha (n))$, nhỏ hơn phần sắp xếp. Bộ nhớ: mảng cạnh $O(m)$ và DSU $O(n)$.
• Prim + heap: mỗi cạnh có thể đẩy một phần tử vào heap (chỉ khi làm giảm key), nên heap có $O(m)$ phần tử, mỗi thao tác $O(\log m)=O(\log n)$ (vì $m\le n^2$ nên $\log m\le 2\log n$).
• Prim mảng: $n$ vòng, mỗi vòng quét $n$ đỉnh để chọn min và $n$ đỉnh để cập nhật: $O(n^2)$. Với $n=2000$, khoảng $8·{10}^6$ phép tính, trong khi Kruskal phải sắp $2·{10}^6$ cạnh và lưu chúng.

Các dạng mở rộng quan trọng

Cây khung lớn nhất

Muốn tổng lớn nhất: chạy Kruskal với cạnh sắp giảm dần (hoặc đổi dấu trọng số rồi chạy MST thường). Hai tính chất lát cắt/chu trình vẫn đúng khi đổi chiều so sánh. Một hệ quả tiện dụng: MST chỉ phụ thuộc vào thứ tự các trọng số, nên cộng một hằng số vào mọi cạnh, hay áp một hàm tăng ngặt bất kỳ, không làm đổi tập các MST (hàm chỉ tăng không ngặt có thể biến hai trọng số khác nhau thành bằng nhau, sinh thêm MST mới); trọng số âm cũng không sao (khác với Dijkstra).

Đường đi minimax nằm trên MST

Bài toán: giữa $u$ và $v$, tìm đường đi sao cho cạnh lớn nhất trên đường là nhỏ nhất (bottleneck path). Đáp án: đường đi giữa $u$ và $v$ trên MST, và giá trị là cạnh lớn nhất trên đường đó.

Vì sao? Gọi $e$ là cạnh lớn nhất trên đường $u\to v$ trong MST $T$, $w(e)=W$. Xóa $e$ khỏi $T$ tách $u$ và $v$ về hai phía của một lát cắt. Mọi đường $u\to v$ trong $G$ đều phải có cạnh $f$ cắt lát cắt này. Nếu $w(f)<W$ thì $T-e+f$ nhẹ hơn $T$, mâu thuẫn; vậy $w(f)\ge W$, tức mọi đường đều có cạnh lớn nhất $\ge W$. Đường trên cây đạt đúng $W$.

Trong ví dụ trên: minimax từ 1 đến 4 là đường cây 1-3-2-4 với cạnh lớn nhất 3 (các đường khác: 1-2-4 cho 4, 1-3-4 cho 5). Minimax từ 1 đến 5 là 6.

Đối xứng: bài "cạnh nhỏ nhất trên đường là lớn nhất" (maximin, ví dụ đường truyền có thông lượng lớn nhất) dùng cây khung lớn nhất và lấy cạnh nhỏ nhất trên đường cây.

Nhìn theo Kruskal: minimax$(u,v)$ chính là trọng số của cạnh mà tại đó $u$ và $v$ lần đầu cùng thành phần. Do đó với truy vấn offline có thể trả lời ngay trong lúc chạy Kruskal; với truy vấn online, dựng MST rồi dùng binary lifting lưu max cạnh trên mỗi bước nhảy:

const int LOG = 17;                      // 2^17 > 1e5
vector<vector<pair<int, int>>> tree;     // MST adjacency: (neighbor, weight)
vector<array<int, LOG>> up, mx;          // 2^k-th ancestor, max edge on that jump
vector<int> dep;

void build(int n, int root) {
    up.assign(n + 1, {}); mx.assign(n + 1, {}); dep.assign(n + 1, 0);
    vector<bool> seen(n + 1, false);
    up[root].fill(root);                 // mx[root] stays 0 (weights >= 0)
    seen[root] = true;
    vector<int> st = {root};
    while (!st.empty()) {                // iterative DFS, no stack overflow
        int u = st.back(); st.pop_back();
        for (auto [v, w] : tree[u]) if (!seen[v]) {
            seen[v] = true; dep[v] = dep[u] + 1;
            up[v][0] = u; mx[v][0] = w;
            for (int k = 1; k < LOG; k++) {   // ancestors are already built
                int mid = up[v][k - 1];
                up[v][k] = up[mid][k - 1];
                mx[v][k] = max(mx[v][k - 1], mx[mid][k - 1]);
            }
            st.push_back(v);
        }
    }
}

int pathMax(int u, int v) {              // max edge on the tree path u..v
    int res = 0;
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; k--)
        if (dep[u] - (1 << k) >= dep[v]) { res = max(res, mx[u][k]); u = up[u][k]; }
    if (u == v) return res;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[u][k] != up[v][k]) {
            res = max({res, mx[u][k], mx[v][k]});
            u = up[u][k]; v = up[v][k];
        }
    return max({res, mx[u][0], mx[v][0]});
}

Bản maximin (trên cây khung lớn nhất). Không chỉ đổi max thành min: giá trị đơn vị của phép min là "vô cùng", không phải 0. Phải đổi cả hai chỗ khởi tạo, nếu không kết quả luôn là 0:

// In build(): replace the max line and initialize the root's table
//     mx[root].fill(INT_MAX);                          // identity of min, NOT 0
//     mx[v][k] = min(mx[v][k - 1], mx[mid][k - 1]);

int pathMin(int u, int v) {              // min edge on the tree path u..v
    int res = INT_MAX;                   // identity of min, NOT 0
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; k--)
        if (dep[u] - (1 << k) >= dep[v]) { res = min(res, mx[u][k]); u = up[u][k]; }
    if (u == v) return res;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[u][k] != up[v][k]) {
            res = min({res, mx[u][k], mx[v][k]});
            u = up[u][k]; v = up[v][k];
        }
    return min({res, mx[u][0], mx[v][0]});
}

Đồ thị không liên thông. build chỉ dựng bảng cho thành phần chứa root. Khi đồ thị có thể không liên thông (ví dụ bài trucktsp), gọi build từ mọi đỉnh chưa thăm (mỗi đỉnh chưa thăm làm gốc một cây mới, chỉ assign mảng một lần), và trước mỗi truy vấn kiểm tra find(u) != find(v) bằng DSU của Kruskal để in $-1$ ngay.

Cạnh tiềm năng: cạnh $e$ có thuộc MST nào đó không?

Từ hai tính chất trên suy ra tiêu chí gọn:

Cạnh $e=(u,v)$ trọng số $w$ thuộc ít nhất một MST khi và chỉ khi $u$ và $v$ không nối được với nhau chỉ bằng các cạnh có trọng số nhỏ hơn hẳn $w$.

• Nếu có đường như vậy, $e$ là cạnh nặng nhất hẳn trên chu trình (đường đó + $e$), loại theo tính chất chu trình.
• Nếu không, cho $e$ đứng đầu nhóm cạnh cùng trọng số $w$ khi chạy Kruskal: lúc xét $e$, $u$ và $v$ vẫn khác thành phần nên $e$ được lấy.

Tương đương: $w\le$ minimax$(u,v)$ tính trên đồ thị bỏ cạnh $e$. Với một cạnh: chạy DSU trên các cạnh nhẹ hơn hẳn $w$, $O(m\alpha (n))$. Với mọi cạnh cùng lúc: xử lý theo nhóm cùng trọng số, kiểm tra cả nhóm trước, rồi mới hợp cả nhóm:

// canBeInMST[i] = true if edge i belongs to at least one MST
vector<bool> potentialEdges(int n, const vector<Edge>& edges) {
    int m = edges.size();
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) { return edges[a].w < edges[b].w; });
    DSU dsu(n);
    vector<bool> canBeInMST(m, false);
    for (int i = 0; i < m; ) {
        int j = i;
        while (j < m && edges[order[j]].w == edges[order[i]].w) j++;
        for (int k = i; k < j; k++) {           // 1) check the whole group first
            const Edge& e = edges[order[k]];
            canBeInMST[order[k]] = dsu.find(e.u) != dsu.find(e.v);
        }
        for (int k = i; k < j; k++)             // 2) then merge the whole group
            dsu.unite(edges[order[k]].u, edges[order[k]].v);
        i = j;
    }
    return canBeInMST;
}

Trong ví dụ: cạnh 1-2 (trọng số 4) không tiềm năng vì 1 và 2 đã nối bằng 1-3-2 với các cạnh 1 và 3 đều $<4$. Nếu đổi trọng số 1-2 thành 3, các cạnh $<3$ chỉ có 1-3 và 2-4, chưa nối 1 với 2, nên 1-2 trở thành tiềm năng (nó "hòa" với cạnh 2-3).

MST khi có trọng số bằng nhau

• Tổng trọng số MST là duy nhất, nhưng cây có thể khác nhau. Mọi MST có cùng số cạnh mỗi trọng số, và sau khi xử lý xong nhóm trọng số $\le w$, các thành phần liên thông giống hệt nhau bất kể chọn cạnh nào trong nhóm. Đây là lý do cách "xử lý theo nhóm" ở trên đúng.
• MST có duy nhất không? Duy nhất khi và chỉ khi ở mọi nhóm, số cạnh tiềm năng (bước 1) bằng số lần unite thành công (bước 2). Nếu nhiều hơn, có cạnh tiềm năng bị bỏ, tức tồn tại MST khác.
• Cạnh thuộc mọi MST: một cạnh tiềm năng thuộc mọi MST khi và chỉ khi nó là cầu trong đồ thị nhỏ gồm các cạnh tiềm năng của nhóm đó (mỗi thành phần DSU co thành một đỉnh). Tìm cầu xem trang cầu và khớp. Đồ thị co này thường có đa cạnh (hai cạnh tiềm năng cùng nối một cặp thành phần DSU, và khi đó không cạnh nào là cầu), nên khi DFS tìm cầu nhớ bỏ qua cạnh cha theo id cạnh, không theo đỉnh cha.
• Nếu trọng số đôi một khác nhau, MST là duy nhất.

Cây khung với đúng $k$ cạnh loại A

Mỗi cạnh có một loại (A hoặc B), và câu hỏi là: cây khung có thể chứa bao nhiêu cạnh loại A? Dạng này xuất hiện khi chi phí chỉ phụ thuộc vào số cạnh mỗi loại (ví dụ hai công ty có bảng giá riêng), hoặc đề ép "đúng $k$ cạnh màu trắng".

Kết quả: các giá trị đạt được là một đoạn liên tục $[k_{min},k_{max}]$.

• $k_{max}$: ưu tiên cạnh A trước. Chạy Kruskal chỉ với cạnh A, số cạnh lấy được là kích thước rừng khung lớn nhất của đồ thị A. Không cây nào chứa nhiều cạnh A hơn (các cạnh A trong cây là một rừng), và rừng này mở rộng thành cây bằng cạnh B nếu đồ thị liên thông.
• $k_{min}$: ưu tiên cạnh B trước. Hợp mọi cạnh B bằng DSU, được $c$ thành phần; rồi duyệt cạnh A, cạnh nào nối hai thành phần khác nhau thì là cạnh bắt buộc. Có đúng $c-1$ cạnh bắt buộc, và đó là $k_{min}$: mọi cây khung phải nối $c$ thành phần B mà cạnh B không nối được, nên cần ít nhất $c-1$ cạnh A. Chữ "bắt buộc" ở đây nghĩa là phải lấy trước khi dựng cây (theo thứ tự duyệt đã chọn), không phải "có mặt trong mọi cây khung": tập cạnh này là một rừng khung của đồ thị co theo các thành phần B, và thứ tự duyệt khác có thể cho tập khác. Ngay ví dụ bên dưới, cây $\{2\text{-}4,1\text{-}2,2\text{-}3\}$ có đúng 1 cạnh A nhưng không chứa $e_1=(3,4)$.
• Mọi giá trị ở giữa đều đạt được nhờ tính chất trao đổi (cây khung là cơ sở của matroid đồ thị): cho hai cây $T$ và $T^{\prime }$, lấy cạnh $f\in T^{\prime }⧵T$; thêm $f$ vào $T$ tạo một chu trình, chu trình đó chứa một cạnh $g\notin T^{\prime }$, và $T-g+f$ vẫn là cây khung. Mỗi bước như vậy làm số cạnh A thay đổi nhiều nhất 1 (bỏ một cạnh, thêm một cạnh) và làm $T$ giống $T^{\prime }$ hơn. Đi từ cây có $k_{min}$ cạnh A tới cây có $k_{max}$ cạnh A theo từng bước $\pm 1$ hoặc $0$, ta đi qua mọi giá trị ở giữa (giống định lý giá trị trung gian).

Dựng cây với đúng $k$ cạnh A ($k_{min}\le k\le k_{max}$), ba bước DSU:

1. Thêm toàn bộ cạnh bắt buộc ($k_{min}$ cạnh).
2. Thêm các cạnh A khác không tạo chu trình cho tới khi đủ $k$ cạnh A. Luôn đủ, vì các cạnh bắt buộc là một rừng con trong đồ thị A, và tham lam mở rộng một rừng A luôn tới được $k_{max}$ cạnh (tính chất tăng cường của matroid).
3. Hoàn tất cây bằng cạnh B. Luôn hoàn tất được, vì cạnh bắt buộc cùng mọi cạnh B đã làm đồ thị liên thông.

Ví dụ: 4 đỉnh, cạnh A: $e_0=(1,3)$, $e_1=(3,4)$, $e_2=(2,4)$; cạnh B: $e_3=(1,2)$, $e_4=(2,3)$.

B trước:  {1,2,3} {4}  ->  e0=(1,3) bỏ, e1=(3,4) BẮT BUỘC, e2=(2,4) bỏ  => kMin = 1
A trước:  e0, e1, e2 đều nhận (1-3-4-2 là cây)                           => kMax = 3

k = 1:  e1 | (không thêm A) | e3=(1,2), e4=(2,3)   -> {3-4, 1-2, 2-3}
k = 2:  e1 | e0=(1,3)       | e3=(1,2)             -> {3-4, 1-3, 1-2}
k = 3:  e1 | e0, e2         | (không cần B)        -> {3-4, 1-3, 2-4}

Cài đặt (dùng lại DSU ở phần Kruskal):

struct TEdge { int u, v; bool isA; };

// Returns {kMin, kMax}; {-1, -1} if the graph is disconnected.
// forced[i] = true if A-edge i is mandatory (bridges two B-components).
pair<int, int> rangeA(int n, const vector<TEdge>& e, vector<bool>& forced) {
    int m = e.size();
    forced.assign(m, false);
    DSU d1(n);                                   // B first, then A
    for (auto& x : e) if (!x.isA) d1.unite(x.u, x.v);
    int kMin = 0, comps = 0;
    for (int i = 0; i < m; i++)
        if (e[i].isA && d1.unite(e[i].u, e[i].v)) forced[i] = true, kMin++;
    for (int v = 1; v <= n; v++) comps += d1.find(v) == v;
    if (comps != 1) return {-1, -1};
    DSU d2(n);                                   // A only
    int kMax = 0;
    for (auto& x : e) if (x.isA && d2.unite(x.u, x.v)) kMax++;
    return {kMin, kMax};
}

// Edge ids of a spanning tree with exactly k A-edges (kMin <= k <= kMax).
vector<int> treeWithK(int n, const vector<TEdge>& e, const vector<bool>& forced, int k) {
    int m = e.size();
    DSU d(n);
    vector<int> res;
    for (int i = 0; i < m; i++)                  // 1) forced A-edges
        if (forced[i]) d.unite(e[i].u, e[i].v), res.push_back(i);
    int cntA = res.size();
    for (int i = 0; i < m && cntA < k; i++)      // 2) extra A-edges up to k
        if (e[i].isA && !forced[i] && d.unite(e[i].u, e[i].v)) res.push_back(i), cntA++;
    for (int i = 0; i < m; i++)                  // 3) finish with B-edges
        if (!e[i].isA && d.unite(e[i].u, e[i].v)) res.push_back(i);
    return res;
}

Độ phức tạp: ba DSU (d1, d2, d), mỗi DSU duyệt danh sách cạnh một vài lượt, tổng $O((n+m)\alpha (n))$. Khi chi phí là $f(k)$ tùy ý (không đơn điệu, không lồi), cứ thử mọi $k\in [k_{min},k_{max}]$ rồi dựng cây một lần cho $k$ tốt nhất.

Có trọng số? Nếu cần MST với đúng $k$ cạnh A (tổng trọng số nhỏ nhất), đoạn $[k_{min},k_{max}]$ vẫn đúng nhưng cách dựng trên không còn tối ưu; khi đó dùng kỹ thuật cộng một hằng số phạt $\lambda$ vào mọi cạnh A rồi tìm kiếm nhị phân trên $\lambda$ (Aliens trick; ý tưởng chung nhắc tới ở DP tối ưu). Khi nhiều cạnh A và B hòa trọng số, cần quy ước phá hòa nhất quán (ví dụ ưu tiên cạnh A khi bằng nhau) và dựng lại cây theo $k$ yêu cầu; phần này trang kia không trình bày chi tiết.

⚠️ Lỗi thường gặp

• Tràn số tổng trọng số. $n={10}^5$ đỉnh nên cây có $n-1\approx {10}^5$ cạnh, mỗi cạnh ${10}^9$, tổng tới ${10}^{14}$. Dùng long long cho total và cho trọng số nếu bình phương khoảng cách ($({10}^6{)}^2$ đã tràn int).
• Đồ thị không liên thông mà vẫn in tổng. Kruskal vẫn chạy hết và trả về tổng của một rừng. Luôn đếm số cạnh đã lấy (taken == n - 1) hoặc số đỉnh đã vào cây (Prim), rồi in -1/IMPOSSIBLE theo đề. Trường hợp $n=1$: đáp án là $0$, vòng lặp không lấy cạnh nào, điều kiện taken == 0 == n - 1 vẫn đúng.
• Binary lifting trên rừng chỉ dựng một cây. Gọi build(n, 1) một lần thì các đỉnh ngoài thành phần của đỉnh 1 có bảng rỗng, truy vấn trả về giá trị rác. Dựng từ mọi đỉnh chưa thăm, và trả lời $-1$ trước bằng DSU khi find(u) != find(v).
• Maximin quên đổi giá trị khởi tạo. Chuyển pathMax sang min mà vẫn để res = 0 (và mx[root] bằng 0) thì mọi truy vấn trả về 0. Giá trị khởi tạo của min phải là INT_MAX.
• DSU không tối ưu. Thiếu cả nén đường lẫn gộp theo kích thước thì find có thể $O(n)$, tổng $O(nm)$ và TLE. Chỉ bỏ nén đường khi cố ý dùng cấu trúc cây DSU (như cách leo cây trong lời giải một số bài VOI), khi đó bắt buộc giữ gộp theo kích thước để độ sâu $O(\log n)$.
• Nhầm MST với cây đường đi ngắn nhất. MST tối thiểu tổng cạnh của cây, không tối thiểu khoảng cách từ một gốc. Đường đi giữa hai đỉnh trên MST không phải đường ngắn nhất (nó chỉ tối ưu theo nghĩa minimax). Muốn khoảng cách ngắn nhất thì dùng Dijkstra.
• Prim: nhầm khóa của heap. Khóa là trọng số cạnh nối vào cây (c), không phải dist[u] + c như Dijkstra. Viết nhầm vẫn ra một cây khung nhưng sai tổng.
• Prim lười quên bỏ bản cũ. Thiếu if (inTree[u]) continue; thì một đỉnh bị cộng trọng số nhiều lần.
• Dùng Kruskal cho đồ thị đầy đủ quá lớn. $n=2000$ điểm cho $2·{10}^6$ cạnh: vẫn chạy được nhưng tốn bộ nhớ, Prim $O(n^2)$ gọn hơn. $n={10}^5$ điểm thì cả hai đều bất khả thi; phải dùng cấu trúc hình học để giảm số cạnh ứng viên xuống $O(n)$ (ví dụ MST Manhattan).
• Kiểm tra cạnh tiềm năng sai dấu hoặc sai thứ tự. Phải dùng cạnh nhẹ hơn hẳn ($<$), không phải $\le$; và khi làm cho mọi cạnh, phải kiểm tra cả nhóm cùng trọng số trước khi hợp bất kỳ cạnh nào trong nhóm. Hợp xen kẽ sẽ đánh dấu sai các cạnh "hòa" là không tiềm năng. Nhớ bỏ chính cạnh đang xét khỏi DSU.
• Maximin dùng nhầm cây. Bài "thông lượng lớn nhất" (cạnh nhỏ nhất trên đường càng lớn càng tốt) cần cây khung lớn nhất và lấy min trên đường; dùng MST thường hoặc lấy max là sai.
• Dựng cây đúng $k$ cạnh A mà không lấy cạnh bắt buộc trước. Thêm $k$ cạnh A tùy ý rồi mới thêm cạnh B có thể không hoàn tất được cây. Ví dụ ở mục trên với $k=1$: lấy $e_0=(1,3)$ thay vì cạnh bắt buộc $e_1$, sau đó cạnh B chỉ nối được $1\text{-}2$, đỉnh 4 bị cô lập. Luôn thêm toàn bộ cạnh bắt buộc trước.
• Đa cạnh, khuyên. Kruskal tự xử lý (khuyên có find(u) == find(v) nên bị bỏ, đa cạnh chỉ lấy cái nhẹ nhất). Với Prim trên ma trận kề, nhớ giữ min khi đọc nhiều cạnh cùng cặp đỉnh.

Biến thể / Mở rộng khác

• Cây khung nhỏ thứ hai: với mỗi cạnh ngoài MST $(u,v,w)$, thử thay cạnh lớn nhất trên đường cây $u\to v$ (tìm bằng pathMax ở trên); lấy chênh lệch nhỏ nhất.
• Cây Kruskal (Kruskal reconstruction tree): mỗi lần hợp hai thành phần, tạo một đỉnh mới làm cha của hai gốc với giá trị bằng trọng số cạnh. Minimax$(u,v)$ là giá trị tại LCA của $u,v$; các đỉnh đi tới được từ $u$ chỉ bằng cạnh $\le x$ là một cây con.
• Borůvka: mỗi vòng, mọi thành phần chọn cạnh nhẹ nhất đi ra ngoài; sau $O(\log n)$ vòng là xong. Hữu ích khi đồ thị ẩn (ví dụ trọng số XOR) và có cách tìm "cạnh nhẹ nhất ra ngoài" nhanh.
• Tính chất trao đổi (exchange): từ một cây khung có thể đổi một cạnh lấy một cạnh khác để thu được cây khung khác. Nhờ đó, các đại lượng như "số cạnh loại A trong cây" chạy liên tục trên một đoạn, dùng trong các bài ràng buộc số cạnh mỗi loại (xem mục "Cây khung với đúng $k$ cạnh loại A" ở trên).
• DSU có rollback cho MST khi cạnh thay đổi theo thời gian (offline): xem DSU rollback.

Bài tập luyện

Luyện kỹ thuật

• Sửa Chữa Đường (roadrepair) (Nghiệp dư) MST cơ bản nhất: cài Kruskal + DSU, nhớ kiểm tra đồ thị không liên thông và dùng long long cho tổng.
• Tưới Ruộng (waterfield) (Trung cấp) đồ thị đầy đủ $N\le 2000$ điểm với trọng số bình phương khoảng cách, chỉ được dùng cạnh $\ge C$: luyện Prim $O(n^2)$ với hàm trọng số trả về vô cùng cho cạnh bị cấm.
• Giải đấu Siêu Bò (Superbull) (Nâng cao) cần nhận ra một giải đấu loại trực tiếp chính là một cây khung; tìm cây khung lớn nhất trên đồ thị đầy đủ trọng số XOR, dùng Prim $O(n^2)$.
• Vận Chuyển Phép Thuật (trucktsp) (Nâng cao) bài maximin kinh điển: cây khung lớn nhất rồi trả lời nhiều truy vấn "cạnh nhỏ nhất trên đường cây" bằng binary lifting, chú ý đồ thị có thể không liên thông.
• Cạnh đầu trong cây khung nhỏ nhất (daleks) (Nâng cao) áp dụng trực tiếp tiêu chí cạnh tiềm năng: trọng số lớn nhất để cạnh vẫn thuộc một MST nào đó chính là minimax giữa hai đầu khi bỏ chính cạnh đó.

Đề VOI

• Nâng cấp mạng (voi11_ugnet) (Nâng cao) VOI 2011: thông lượng tốt nhất giữa hai máy là bài maximin, trả lời bằng cạnh nhỏ nhất trên đường đi trong cây khung lớn nhất; chỉ các cáp ngoài cây cần nâng.
• Mạng truyền thông (voi13_comnet) (Nâng cao) VOI 2013. Gợi ý: mỗi giả định chính là câu hỏi "cạnh tiềm năng" với chi phí mới. Chú ý dấu nhỏ hơn hẳn và bỏ chính cạnh $k$.
• Mạng truyền thông (voi14_aznet) (Kỳ cựu) VOI 2014: chi phí chỉ phụ thuộc số kênh công ty A trong cây; nhờ tính chất trao đổi, số đó chạy trên một đoạn liên tục, tìm hai đầu đoạn bằng hai lượt Kruskal ưu tiên loại khác nhau (xem mục Cây khung với đúng $k$ cạnh loại A).
• Trò chơi (voi17_bgame) (Nâng cao) VOI 2017: thêm cạnh theo số chuối giảm dần như Kruskal cây khung lớn nhất; mỗi cạnh ngoài cây đóng một chu trình mà mọi cạnh trên đó đều không nhẹ hơn nó, kết hợp với ý thành phần song liên thông cạnh.
• Kết nối internet (voi22_inet) (Kỳ cựu) VOI 2022: các nhóm ban đầu là thành phần khi chỉ giữ cạnh $\le s$, và $k$ dây cáp rẻ nhất là $k$ cạnh tiếp theo Kruskal nhận; khó ở chỗ phải dựng MST Manhattan chỉ với $O(n)$ cạnh ứng viên.