Minimum Spanning Tree

Kruskal

Tính chất cắt. Chia đỉnh thành hai phần bất kỳ; cạnh nhẹ nhất nối hai phần thuộc một MST nào đó. Nếu một cây khung không dùng nó, thêm nó vào tạo chu trình, chu trình đó phải có một cạnh khác cũng nối hai phần, nặng hơn hoặc bằng; bỏ cạnh đó ra được một cây khung không tệ hơn.

Tính chất chu trình. Cạnh nặng nhất của một chu trình luôn bỏ được: có một MST không dùng nó, vì đi vòng qua phần còn lại của chu trình chỉ tốn các cạnh không nặng hơn. Mục cuối bài dùng kỹ tính chất này.

Kruskal. Sắp cạnh tăng theo trọng số, lần lượt xét: hai đầu khác thành phần thì lấy cạnh và gộp hai thành phần, cùng thành phần thì bỏ. Mỗi cạnh được lấy là cạnh nhẹ nhất nối thành phần của một đầu với phần còn lại, nên đúng theo tính chất cắt. Chi phí $O(m \log m)$ cho việc sắp, DSU gần như $O(1)$ mỗi cạnh. Kết thúc với ít hơn $n - 1$ cạnh nghĩa là đồ thị không liên thông.

Ví dụMạng Kết Nối Tiết Kiệm

Đề. $n \le 10^5$ trạm, $m \le 2 \cdot 10^5$ tuyến có chi phí. Tìm tổng chi phí nhỏ nhất để nối mọi trạm, hoặc IMPOSSIBLE.

Lời giải. Kruskal: duyệt cạnh theo chi phí tăng dần, lấy cạnh nào nối hai thành phần khác nhau. Đúng theo tính chất cắt: cạnh nhẹ nhất đi qua lát cắt giữa một thành phần và phần còn lại luôn thuộc một cây khung nhỏ nhất. Đếm số cạnh đã lấy; chưa đủ $n - 1$ cạnh thì đồ thị không liên thông.

Bước 1: DSU. find nén đường đi; unite hợp theo kích thước và trả về có hợp được hay không.

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool unite(ll u, ll v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

Bước 2: sắp cạnh theo chi phí. Mỗi cạnh là array (chi phí, u, v), đặt chi phí ở đầu để sort sắp theo nó.

for (ll i = 1; i <= m; i++) cin >> e[i][1] >> e[i][2] >> e[i][0];
sort(e + 1, e + m + 1);

Bước 3: lấy cạnh.

for (ll i = 1; i <= m; i++)
    if (unite(e[i][1], e[i][2])) {
        cost += e[i][0];
        cnt++;
    }

Tổng tới $10^{14}$, cần ll.

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

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, par[N], sz[N];
array<ll, 3> e[M];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool unite(ll u, ll v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    for (ll i = 1; i <= m; i++) cin >> e[i][1] >> e[i][2] >> e[i][0];
    sort(e + 1, e + m + 1);
    ll cost = 0, cnt = 0;
    for (ll i = 1; i <= m; i++)
        if (unite(e[i][1], e[i][2])) {
            cost += e[i][0];
            cnt++;
        }
    if (cnt < n - 1) cout << "IMPOSSIBLE\n";
    else cout << cost << '\n';
}

ChạyInput4 5
1 2 4
1 3 9
2 3 2
2 4 7
3 4 3

Output9

$O(m \log m)$ cho phần sắp.

Gộp đỉnh, dừng sớm

Nguồn chung. Yêu cầu “mỗi thành phần chứa đúng một nhà máy” là cây khung của đồ thị trong đó mọi nhà máy được gộp thành một đỉnh. Với DSU, chỉ cần gộp sẵn các nhà máy vào cùng một nhóm trước khi chạy Kruskal: cáp nối hai nhà máy khi đó có hai đầu cùng nhóm và bị bỏ. Tương tự, “xây trạm tại đỉnh $i$ tốn $c_i$” là cạnh từ một đỉnh ảo 0 tới $i$ nặng $c_i$.

Dừng sớm. Kruskal gộp thành phần theo thứ tự cạnh tăng dần. Dừng khi còn đúng $k$ thành phần thì được rừng $k$ cây có tổng nhỏ nhất, cũng là MST bỏ đi $k - 1$ cạnh nặng nhất, tức sau khi lấy $n - k$ cạnh. Đó là cách phân cụm theo khoảng cách: cạnh tiếp theo không được lấy là khoảng cách nhỏ nhất giữa hai cụm.

Prim

Prim mọc cây từ một đỉnh: giữ $d_v$ là cạnh rẻ nhất nối $v$ với cây hiện tại; mỗi bước lấy đỉnh ngoài cây có $d$ nhỏ nhất, thêm vào cây với cạnh đó, rồi cập nhật $d$ của các đỉnh khác. Mỗi bước đúng theo tính chất cắt (cắt giữa cây và phần còn lại). Với đồ thị đầy đủ $n^2$ cạnh, bản không dùng hàng đợi, mỗi bước tìm min bằng một vòng lặp, tốn $O(n^2)$ và không cần lưu danh sách cạnh. Đồ thị thưa thì dùng hàng đợi ưu tiên như Dijkstra, $O(m \log n)$.

Ví dụMạng Kết Nối Dày

Đề. $n \le 1000$ nút, chi phí nối mọi cặp cho bằng ma trận $n \times n$. Tìm tổng chi phí nhỏ nhất để nối mọi nút.

Lời giải. Đồ thị đầy đủ có $5 \cdot 10^5$ cạnh; Kruskal phải sắp hết chúng. Prim trực tiếp trên ma trận chỉ tốn $O(n^2) = 10^6$ phép và không cần danh sách cạnh: mọc cây từ đỉnh 1, mỗi bước thêm đỉnh ngoài cây nối với cây bằng cạnh rẻ nhất.

Bước 1: nhãn của đỉnh ngoài cây. d[v] là cạnh rẻ nhất nối $v$ với cây hiện tại, in[v] đánh dấu đã vào cây. Bắt đầu với d[1] = 0.

for (ll i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;

Bước 2: $n$ vòng. Mỗi vòng tìm đỉnh ngoài cây có d nhỏ nhất bằng một vòng lặp $O(n)$, đưa vào cây và cộng d của nó, rồi cập nhật d của các đỉnh còn lại qua cạnh từ đỉnh vừa thêm.

for (ll it = 1; it <= n; it++) {
    ll u = 0;
    for (ll v = 1; v <= n; v++)
        if (!in[v] && (!u || d[v] < d[u])) u = v;
    in[u] = 1;
    cost += d[u];
    for (ll v = 1; v <= n; v++)
        if (!in[v]) d[v] = min(d[v], c[u][v]);
}

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

const ll N = 1005, INF = 1e18;
ll n, c[N][N], d[N], in[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) cin >> c[i][j];
    for (ll i = 1; i <= n; i++) d[i] = INF;
    d[1] = 0;
    ll cost = 0;
    for (ll it = 1; it <= n; it++) {
        ll u = 0;
        for (ll v = 1; v <= n; v++)
            if (!in[v] && (!u || d[v] < d[u])) u = v;
        in[u] = 1;
        cost += d[u];
        for (ll v = 1; v <= n; v++)
            if (!in[v]) d[v] = min(d[v], c[u][v]);
    }
    cout << cost << '\n';
}

ChạyInput5
0 4 9 8 7
4 0 2 6 5
9 2 0 3 10
8 6 3 0 1
7 5 10 1 0

Output10

$O(n^2)$.

So với Kruskal trên cùng đồ thị đầy đủ:

Prim nhanh hơn Kruskal khoảng 15 lần, vì Kruskal phải sắp 4,5 triệu cạnh. Đồ thị dày thì dùng Prim, đồ thị thưa thì Kruskal.

Cạnh có thể dùng

Đồ thị đầy đủ $n = 10^5$ đỉnh có $5 \cdot 10^9$ cạnh, không thể liệt kê. Nhưng theo tính chất chu trình, cạnh nặng nhất của bất kỳ chu trình nào cũng bỏ được. Khi trọng số có cấu trúc, thường chỉ $O(n)$ cạnh có thể thuộc MST.

Ví dụ với chi phí $\min(|x_i - x_j|, |y_i - y_j|)$: sắp theo $x$, cạnh giữa hai điểm không kề nhau theo $x$ có phần $|x_i - x_j|$ bằng tổng các khoảng kề ở giữa, mỗi khoảng là một cạnh nhẹ hơn hoặc bằng, nên chỉ cần $n - 1$ cạnh kề theo $x$ cộng $n - 1$ cạnh kề theo $y$.

Ví dụNối Thành Phố Theo Trục

Đề. $n \le 10^5$ thành phố trên mặt phẳng, đường giữa hai thành phố tốn $\min(|x_i - x_j|, |y_i - y_j|)$. Tìm tổng chi phí nhỏ nhất để nối tất cả.

Lời giải. Không thể xét $n^2$ cặp. Nhận xét: chỉ cần các cạnh giữa hai thành phố kề nhau khi sắp theo $x$ (chi phí hiệu $x$) và kề nhau khi sắp theo $y$ (chi phí hiệu $y$), tổng $2(n - 1)$ cạnh. Chi phí dùng cho một cạnh có thể lớn hơn chi phí thật $\min(|\Delta x|, |\Delta y|)$, nhưng cùng cặp đó, hoặc một đường rẻ không kém, cũng có mặt trong danh sách của trục kia, nên tổng nhỏ nhất không đổi.

Bước 1: cạnh theo từng trục. id sắp theo $x$, thêm $n - 1$ cạnh giữa hai thành phố kề nhau; rồi sắp lại theo $y$ và làm tương tự.

sort(id + 1, id + n + 1, byx);
for (ll i = 1; i < n; i++) e.push_back({x[id[i + 1]] - x[id[i]], id[i], id[i + 1]});
sort(id + 1, id + n + 1, byy);
for (ll i = 1; i < n; i++) e.push_back({y[id[i + 1]] - y[id[i]], id[i], id[i + 1]});

Bước 2: Kruskal trên $2(n - 1)$ cạnh.

sort(e.begin(), e.end());
for (array<ll, 3> t : e) {
    ll u = find(t[1]), v = find(t[2]);
    if (u == v) continue;
    par[u] = v;
    cost += t[0];
}

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

const ll N = 1e5 + 5;
ll n, x[N], y[N], id[N], par[N];
vector<array<ll, 3>> e;

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool byx(ll a, ll b) {
    return x[a] < x[b];
}

bool byy(ll a, ll b) {
    return y[a] < y[b];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        id[i] = par[i] = i;
    }
    sort(id + 1, id + n + 1, byx);
    for (ll i = 1; i < n; i++) e.push_back({x[id[i + 1]] - x[id[i]], id[i], id[i + 1]});
    sort(id + 1, id + n + 1, byy);
    for (ll i = 1; i < n; i++) e.push_back({y[id[i + 1]] - y[id[i]], id[i], id[i + 1]});
    sort(e.begin(), e.end());
    ll cost = 0;
    for (array<ll, 3> t : e) {
        ll u = find(t[1]), v = find(t[2]);
        if (u == v) continue;
        par[u] = v;
        cost += t[0];
    }
    cout << cost << '\n';
}

ChạyInput5
0 0
5 2
6 10
12 9
20 3

Output5

$O(n \log n)$.

Cạnh nào vào cây

Tính chất chu trình. Nếu cạnh $(u, v, w)$ nặng hơn hẳn mọi cạnh trên một đường từ $u$ tới $v$, nó không thuộc MST nào. Hệ quả: với trọng số khác nhau, cạnh $(u, v, w)$ thuộc MST khi và chỉ khi các cạnh nhẹ hơn $w$ chưa nối được $u$ với $v$, tức lúc Kruskal tới $w$ thì $u$ và $v$ còn khác thành phần. Nhiều câu hỏi “thêm cạnh này thì nó có vào cây không” giải ngoại tuyến: trộn cạnh câu hỏi vào danh sách đã sắp, tới cạnh câu hỏi thì chỉ kiểm DSU mà không gộp.

Cây nhỏ nhất bắt buộc chứa một cạnh. Thêm $(u, v, w)$ vào MST tạo một chu trình gồm nó và đường $(u, v)$ trên cây; bỏ cạnh nặng nhất trên đường đó. Tổng mới là $\text{MST} - \max(u, v) + w$, với $\max(u, v)$ là cạnh nặng nhất trên đường trong cây, tính bằng LCA kèm max (bài 36).

Ví dụCạnh Thử Trong Cây Khung

Đề. Đồ thị liên thông $n, m \le 2 \cdot 10^5$ với trọng số khác nhau, $q \le 2 \cdot 10^5$ câu hỏi độc lập: thêm cạnh $(u, v, w)$ thì nó có thuộc MST không.

Lời giải. Cạnh $(u, v, w)$ thêm vào được Kruskal chọn khi và chỉ khi các cạnh nhẹ hơn $w$ chưa nối được $u$ với $v$. Vậy trộn cạnh gốc và cạnh câu hỏi, sắp theo trọng số (mọi trọng số khác nhau nên không có hòa), rồi chạy Kruskal: gặp cạnh gốc thì gộp, gặp cạnh câu hỏi thì chỉ kiểm hai đầu còn khác thành phần không. Không gộp cạnh câu hỏi, vì các câu hỏi độc lập.

Bước 1: một danh sách chung. Mỗi phần tử là (trọng số, u, v, chỉ số câu hỏi); cạnh gốc có chỉ số 0.

for (ll i = 1; i <= m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    e.push_back({c, a, b, 0});
}
for (ll i = 1; i <= q; i++) {
    ll u, v, w;
    cin >> u >> v >> w;
    e.push_back({w, u, v, i});
}

Bước 2: Kruskal có câu hỏi xen kẽ.

sort(e.begin(), e.end());
for (array<ll, 4> t : e) {
    ll u = find(t[1]), v = find(t[2]);
    if (t[3]) ans[t[3]] = (u != v);
    else if (u != v) par[u] = v;
}

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

const ll N = 2e5 + 5;
ll n, m, q, par[N], ans[N];
vector<array<ll, 4>> e;

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (ll i = 1; i <= n; i++) par[i] = i;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        e.push_back({c, a, b, 0});
    }
    for (ll i = 1; i <= q; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        e.push_back({w, u, v, i});
    }
    sort(e.begin(), e.end());
    for (array<ll, 4> t : e) {
        ll u = find(t[1]), v = find(t[2]);
        if (t[3]) ans[t[3]] = (u != v);
        else if (u != v) par[u] = v;
    }
    for (ll i = 1; i <= q; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
}

+12 dòngChạyInput5 6 5
1 2 2
2 3 5
1 3 9
3 4 12
4 5 15
2 5 20
1 3 1
1 3 3
1 3 7
2 4 10
1 5 25

OutputYes
Yes
No
Yes
No

$O((m + q) \log (m + q))$.

Ví dụCây Khung Bắt Buộc Từng Cạnh

Đề. Đồ thị liên thông $n, m \le 2 \cdot 10^5$. Với từng cạnh, in tổng nhỏ nhất của một cây khung bắt buộc chứa cạnh đó.

Lời giải. Lấy cây khung nhỏ nhất (tổng $S$). Bắt buộc có cạnh $(u, v, w)$: thêm nó vào cây tạo đúng một chu trình, gồm cạnh đó và đường $(u, v)$ trên cây; bỏ cạnh nặng nhất của đường cũ cho cây tốt nhất chứa cạnh này. Đáp án là $S - \max_{\text{đường}}(u, v) + w$. Cạnh thuộc cây có cạnh nặng nhất trên đường chính bằng nó, nên đáp án là $S$.

Bước 1: Kruskal dựng cây. Sắp chỉ số cạnh theo trọng số, cộng $S$ và thêm cạnh được chọn vào danh sách kề của cây.

for (ll k = 1; k <= m; k++) {
    ll i = id[k], u = find(eu[i]), v = find(ev[i]);
    if (u == v) continue;
    par[u] = v;
    S += ew[i];
    g[eu[i]].push_back({ev[i], ew[i]});
    g[ev[i]].push_back({eu[i], ew[i]});
}

Bước 2: bảng nhảy kèm cạnh nặng nhất. BFS trên cây: up[0][v] là cha, mx[0][v] là trọng số cạnh $v$ với cha; các tầng sau gộp mx như bài 36.

for (ll j = 1; j < LG; j++)
    for (ll v = 1; v <= n; v++) {
        up[j][v] = up[j - 1][up[j - 1][v]];
        mx[j][v] = max(mx[j - 1][v], mx[j - 1][up[j - 1][v]]);
    }

Bước 3: cạnh nặng nhất trên đường. pmax(a, b) đi đúng hai pha tìm LCA, gộp mx của mỗi đoạn nhảy và hai cạnh cuối.

ll pmax(ll a, ll b) {
    ll res = 0;
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) {
            res = max(res, mx[j][a]);
            a = up[j][a];
        }
    if (a == b) return res;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) {
            res = max({res, mx[j][a], mx[j][b]});
            a = up[j][a];
            b = up[j][b];
        }
    return max({res, mx[0][a], mx[0][b]});
}

Trọng số và tổng tới $10^{14}$, dùng long long.

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

const ll N = 2e5 + 5, LG = 18;
ll n, m, par[N], dep[N], up[LG][N], mx[LG][N], eu[N], ev[N], ew[N], id[N];
vector<pair<ll, ll>> g[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool cmp(ll a, ll b) {
    return ew[a] < ew[b];
}

ll pmax(ll a, ll b) {
    ll res = 0;
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) {
            res = max(res, mx[j][a]);
            a = up[j][a];
        }
    if (a == b) return res;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) {
            res = max({res, mx[j][a], mx[j][b]});
            a = up[j][a];
            b = up[j][b];
        }
    return max({res, mx[0][a], mx[0][b]});
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> ew[i];
        id[i] = i;
    }
    for (ll i = 1; i <= n; i++) par[i] = i;
    sort(id + 1, id + m + 1, cmp);
    ll S = 0;
    for (ll k = 1; k <= m; k++) {
        ll i = id[k], u = find(eu[i]), v = find(ev[i]);
        if (u == v) continue;
        par[u] = v;
        S += ew[i];
        g[eu[i]].push_back({ev[i], ew[i]});
        g[ev[i]].push_back({eu[i], ew[i]});
    }
    vector<ll> ord = {1};
    up[0][1] = 1;
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (pair<ll, ll> e : g[u])
            if (e.first != up[0][u]) {
                up[0][e.first] = u;
                mx[0][e.first] = e.second;
                dep[e.first] = dep[u] + 1;
                ord.push_back(e.first);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) {
            up[j][v] = up[j - 1][up[j - 1][v]];
            mx[j][v] = max(mx[j - 1][v], mx[j - 1][up[j - 1][v]]);
        }
    for (ll i = 1; i <= m; i++) cout << S - pmax(eu[i], ev[i]) + ew[i] << '\n';
}

ChạyInput4 5
1 2 1
2 3 2
3 4 3
1 4 10
1 3 4

Output6
6
6
13
8

$O((n + m) \log n)$.