Cây khung nhỏ nhất

Mức độ: Nâng cao

Có n thành phố và danh sách các con đường có thể xây, mỗi con đường có chi phí. Cần xây một số con đường để mọi thành phố đi được tới nhau, tổng chi phí ít nhất. Tập đường tốt nhất không bao giờ có vòng (bỏ một cạnh của vòng vẫn liên thông mà rẻ hơn), nên nó là một cây đi qua mọi đỉnh: cây khung nhỏ nhất (MST).

Thuật toán Kruskal

1. Sắp xếp các cạnh theo chi phí tăng dần.
2. Lần lượt xét từng cạnh (u, v): nếu u và v chưa đi được tới nhau thì chọn cạnh đó; nếu đã đi được tới nhau thì bỏ qua (thêm vào sẽ tạo vòng).
3. Dừng khi đã chọn n - 1 cạnh.

Kiểm tra “u và v đã đi được tới nhau chưa” và gộp hai nhóm bằng DSU.

Bốn thành phố, các cạnh (u, v, chi phí): (1, 2, 1), (2, 3, 2), (1, 3, 3), (3, 4, 4), (2, 4, 5):

Cạnh	Chi phí	Việc làm	Các nhóm
1-2	1	chọn	1 2 | 3 | 4
2-3	2	chọn	1 2 3 | 4
1-3	3	bỏ (1, 3 đã cùng nhóm)	1 2 3 | 4
3-4	4	chọn	1 2 3 4

Tổng chi phí 7.

Vì sao tham lam đúng? Xét cạnh e rẻ nhất nối hai nhóm khác nhau A và B. Nếu một cây khung tốt nhất T không chứa e, thêm e vào T tạo một vòng; vòng này phải đi qua một cạnh f khác cũng nối A với B. Chi phí f không nhỏ hơn e, nên bỏ f thay bằng e được một cây khung không đắt hơn. Vậy luôn có cây khung tốt nhất chứa e.

Python

import sys
du_lieu = sys.stdin.read().split()
n, m = int(du_lieu[0]), int(du_lieu[1])
canh = sorted((int(du_lieu[4 + 3 * i]), int(du_lieu[2 + 3 * i]), int(du_lieu[3 + 3 * i])) for i in range(m))
cha = list(range(n + 1))

def tim(x):
    while cha[x] != x:
        cha[x] = cha[cha[x]]
        x = cha[x]
    return x

tong, so_canh = 0, 0
for w, u, v in canh:                     # đã sắp xếp theo chi phí
    gu, gv = tim(u), tim(v)
    if gu != gv:
        cha[gu] = gv
        tong += w
        so_canh += 1
print(tong if so_canh == n - 1 else "IMPOSSIBLE")

C++

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <numeric>
using namespace std;

vector<int> cha;

int tim(int x) {
    while (cha[x] != x) x = cha[x] = cha[cha[x]];
    return x;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<long long, int, int>> canh(m);
    for (auto &[w, u, v] : canh) cin >> u >> v >> w;
    sort(canh.begin(), canh.end());              // theo chi phí tăng dần
    cha.resize(n + 1);
    iota(cha.begin(), cha.end(), 0);
    long long tong = 0;
    int soCanh = 0;
    for (auto [w, u, v] : canh) {
        int gu = tim(u), gv = tim(v);
        if (gu != gv) {
            cha[gu] = gv;
            tong += w;
            soCanh++;
        }
    }
    if (soCanh == n - 1) cout << tong << "\n";
    else cout << "IMPOSSIBLE\n";
    return 0;
}

Sắp xếp mất m × log₂m bước, phần còn lại gần như m bước.

Thuật toán Prim

Prim mọc cây từ một đỉnh, giống Dijkstra: mỗi bước thêm vào cây đỉnh ngoài cây nối với cây bằng cạnh rẻ nhất. Khác Dijkstra ở chỗ khóa của đỉnh v là chi phí của một cạnh nối v với cây, không phải tổng đường đi. Prim hợp với đồ thị dày (cho bằng bảng chi phí giữa mọi cặp): không cần hàng đợi ưu tiên, mỗi bước tìm đỉnh có khóa nhỏ nhất bằng cách quét, cả bài n² bước.

Những bài cùng ý tưởng

Đề hỏi	Cách làm
cây khung lớn nhất	Kruskal với cạnh sắp xếp giảm dần
cạnh đắt nhất trong cây là nhỏ nhất có thể	chính là cạnh đắt nhất của cây khung nhỏ nhất
chia thành k nhóm, khoảng cách giữa các nhóm lớn nhất	Kruskal dừng khi còn k nhóm
một số đỉnh được “đặt trạm” với chi phí riêng	thêm một đỉnh ảo 0, nối với mỗi đỉnh bằng cạnh có chi phí đặt trạm

Luyện tập

Gồm 13 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Kruskal

Bài 1. Chi phí nối mọi thành phố

Có n thành phố và m con đường có thể xây, đường thứ i nối u, v với chi phí w. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra tổng chi phí ít nhất để mọi thành phố đi được tới nhau, hoặc IMPOSSIBLE.

Ví dụ:

Nhập	In ra
4 5 1 2 1 2 3 2 1 3 3 3 4 4 2 4 5	7

Kiểm tra: nhập

6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

Xem đáp số

33

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Cây khung lớn nhất

Có n trạm và m đường truyền, đường thứ i nối u, v có chất lượng w. Chọn n - 1 đường truyền để mọi trạm liên lạc được với nhau và tổng chất lượng lớn nhất. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra tổng lớn nhất, hoặc IMPOSSIBLE.

Ví dụ:

Nhập	In ra
4 5 1 2 1 2 3 2 1 3 3 3 4 4 2 4 5	12

Kiểm tra: nhập

6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

Xem đáp số

58

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Con đường dốc nhất nhỏ nhất

Có n thành phố và m con đường hai chiều, đường thứ i có độ dốc w. Chọn một số con đường để mọi thành phố đi được tới nhau sao cho độ dốc lớn nhất trong các con đường được chọn là nhỏ nhất. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra độ dốc đó, hoặc IMPOSSIBLE.

Ví dụ:

Nhập	In ra
4 5 1 2 1 2 3 2 1 3 3 3 4 4 2 4 5	4

Kiểm tra: nhập

6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

Xem đáp số

9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Một số đường đã có sẵn

Có n thành phố, m con đường có thể xây với chi phí, và k con đường đã có sẵn (miễn phí). Dòng đầu có n, m, k (1 ≤ n ≤ 10⁵, 0 ≤ m, k ≤ 2 × 10⁵), k dòng sau mỗi dòng có u, v (đường có sẵn), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra chi phí xây thêm ít nhất để mọi thành phố đi được tới nhau, hoặc IMPOSSIBLE.

Ví dụ:

Nhập	In ra
4 3 1 1 3 1 2 5 2 4 2 3 4 4	6

Kiểm tra: nhập

6 6 2
1 2
5 6
2 3 4
1 3 2
3 4 7
4 5 1
2 6 9
3 5 3

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Giếng và ống nước

Có n làng. Làng i tự đào giếng tốn c_i. Có m đường ống có thể xây, ống thứ j nối hai làng u, v tốn w (làng nối ống với làng có nước thì cũng có nước). Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), dòng thứ hai có n số c_i, m dòng sau mỗi dòng có u, v, w (1 ≤ c, w ≤ 10⁹). In ra chi phí ít nhất để làng nào cũng có nước.

Ví dụ:

Nhập	In ra
3 2 1 2 2 1 2 1 2 3 1	3

Kiểm tra: nhập

5 6
10 8 12 3 9
1 2 4
2 3 5
3 4 6
4 5 7
1 5 2
2 4 1

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Prim trên đồ thị dày

Bài 6. Bảng chi phí giữa mọi cặp

Có n thành phố, chi phí nối trực tiếp thành phố i với j là c_ij (c_ij = c_ji, c_ii = 0). Dòng đầu có n (1 ≤ n ≤ 1500), n dòng sau mỗi dòng có n số (0 ≤ c_ij ≤ 10⁶). In ra tổng chi phí ít nhất để nối mọi thành phố.

Ví dụ:

Nhập	In ra
4 0 2 6 5 2 0 3 8 6 3 0 4 5 8 4 0	9

Kiểm tra: nhập

5
0 7 3 9 4
7 0 8 2 6
3 8 0 5 1
9 2 5 0 7
4 6 1 7 0

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nối các điểm bằng dây đi theo ô

Có n điểm trên lưới, điểm i ở (x_i, y_i). Nối hai điểm tốn chi phí bằng khoảng cách |x_i - x_j| + |y_i - y_j|. Dòng đầu có n (1 ≤ n ≤ 2000), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁶). In ra tổng chi phí ít nhất để nối mọi điểm.

Ví dụ:

Nhập	In ra
5 0 0 2 2 3 10 5 2 7 0	20

Kiểm tra: nhập

6
-4 3
1 1
6 -2
0 8
-3 -5
2 2

Xem đáp số

34

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Biến đổi đề

Bài 8. Chia thành k cụm

Có n điểm trên mặt phẳng. Chia các điểm thành đúng k cụm (mỗi cụm khác rỗng) sao cho khoảng cách nhỏ nhất giữa hai điểm thuộc hai cụm khác nhau là lớn nhất. Khoảng cách là bình phương khoảng cách Euclid (x - x’)² + (y - y’)². Dòng đầu có n, k (2 ≤ k ≤ n ≤ 1000), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁴, các điểm khác nhau). In ra khoảng cách nhỏ nhất đó.

Ví dụ:

Nhập	In ra
6 3 0 0 1 0 10 0 11 1 20 20 21 20	81

Kiểm tra: nhập

8 2
0 0
0 3
4 0
50 50
52 51
49 53
100 0
103 4

Xem đáp số

4810

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Nối các điểm trên một đường thẳng

Có n trạm trên một con đường thẳng, trạm i ở km x_i. Nối hai trạm tốn chi phí bằng khoảng cách giữa chúng. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số x_i (0 ≤ x_i ≤ 10⁹). In ra tổng chi phí ít nhất để nối mọi trạm.

Ví dụ:

Nhập	In ra
4 7 1 4 12	11

Kiểm tra: nhập

8
100 3 58 1000000000 17 64 64 250

Xem đáp số

999999997

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Cây khung trên bảng độ cao

Bảng h hàng, w cột, mỗi ô có độ cao. Xây đường giữa hai ô chung cạnh tốn chi phí bằng chênh lệch độ cao của hai ô. Dòng đầu có h, w (1 ≤ h, w ≤ 300), h dòng sau mỗi dòng có w số (0 ≤ độ cao ≤ 10⁶). In ra tổng chi phí ít nhất để mọi ô đi được tới nhau.

Ví dụ:

Nhập	In ra
2 3 1 5 2 4 3 7	13

Kiểm tra: nhập

3 4
10 12 30 31
50 15 16 70
9 80 18 19

Xem đáp số

201

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đường được thưởng

Có n thành phố và m con đường có thể xây, đường thứ i có chi phí w (w âm nghĩa là xây xong được thưởng -w). Phải xây sao cho mọi thành phố đi được tới nhau, được phép xây thêm đường tùy ý (kể cả tạo vòng). Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (|w| ≤ 10⁹). In ra tổng chi phí ít nhất, hoặc IMPOSSIBLE.

Ví dụ:

Nhập	In ra
4 5 1 2 3 2 3 -2 1 3 -1 3 4 4 2 4 1	-2

Kiểm tra: nhập

5 7
1 2 5
2 3 -3
3 1 -4
3 4 2
4 5 6
2 5 1
1 5 -2

Xem đáp số

-7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Câu hỏi trên cây khung

Bài 12. Cạnh dốc nhất trên đường đi

Có n thành phố, m con đường hai chiều có độ dốc, và q câu hỏi. Mỗi câu hỏi a, b: trong mọi đường đi từ a tới b, độ dốc lớn nhất của đường đi đó nhỏ nhất là bao nhiêu? Dòng đầu có n, m, q (2 ≤ n ≤ 1000, 0 ≤ m ≤ 5000, 1 ≤ q ≤ 1000), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹), q dòng sau mỗi dòng có a, b (a khác b). In ra đáp số mỗi câu hỏi, hoặc -1 nếu không tới được.

Ví dụ:

Nhập	In ra
5 6 3 1 2 4 2 3 3 1 3 7 3 4 2 4 5 6 2 5 8 1 3 1 5 4 2	4 6 3

Kiểm tra: nhập

6 8 4
1 2 5
2 3 9
3 4 2
4 5 8
5 6 1
1 6 10
2 5 3
3 6 7
1 4
2 6
3 5
1 6

Xem đáp số

7
3
7
5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Cây khung tốt thứ hai

Có n thành phố, m con đường có thể xây với chi phí khác nhau đôi một, đồ thị liên thông. Dòng đầu có n, m (2 ≤ n ≤ 200, n - 1 ≤ m ≤ 2000), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁶, các w khác nhau). Gọi S là tổng chi phí của cây khung nhỏ nhất. In ra tổng chi phí nhỏ nhất của một cây khung khác cây khung nhỏ nhất, hoặc -1 nếu không có cây khung nào khác.

Ví dụ:

Nhập	In ra
4 5 1 2 1 2 3 2 1 3 3 3 4 4 2 4 5	8

Kiểm tra: nhập

5 7
1 2 3
2 3 4
3 4 6
4 5 7
1 5 10
2 4 5
1 3 8

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.