+3

Bài toán cây khung nhỏ nhất

I. Giới thiệu chung

Những giải thuật trên đồ thị luôn luôn là một chủ đề khiến cho chúng ta phải đau đầu, đặc biệt là với những ai đang nghiên cứu về chủ đề Cấu trúc dữ liệu & Giải thuật. Một trong số những bài toán kinh điển của chủ đề Đồ thị là Bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree). Đây là một bài toán có lịch sử lâu đời và có ứng dụng nhiều trong thực tế đời sống. Tuy nhiên, trước hết chúng ta sẽ cùng tìm hiểu về một số khái niệm cần thiết trong chuyên đề này.

Lưu ý rằng, trong bài toán này sẽ sử dụng tới cấu trúc dữ liệu Disjoint Sets Union (DSU).

1. Cây khung của đồ thị (Spanning Trees)

Như ta đã biết, đồ thị vô hướng G(V,E)G(V, E) là một đồ thị có tập đỉnh là VV và tập cạnh là E,E, với các cạnh đều vô hướng. Một cây khung của đồ thị là một tập các cạnh của đồ thị thỏa mãn hai điều kiện:

  • Tập cạnh này không chứa chu trình.
  • Tập cạnh này liên thông và chứa tất cả các đỉnh của đồ thị.

Nói cách khác, nếu đồ thị gồm nn đỉnh thì cây khung của đồ thị là một đồ thị con liên thông chứa đủ nn đỉnh và n1n - 1 cạnh của đồ thị ban đầu.

Một đồ thị có thể có một hoặc nhiều cây khung. Hình vẽ dưới đây minh họa các cây khung có thể có trên một đồ thị vô hướng không có trọng số:

<center>

</center>

Trong chuyên đề này, chúng ta sẽ chỉ làm việc với cây khung trên đồ thị vô hướng. Thực tế thì các bài toán về cây khung cũng chỉ hầu hết cho trên đồ thị vô hướng mà thôi.

2. Cây khung nhỏ nhất (Minimum Spanning Tree)

Xét một đồ thị vô hướng G(V,E)G(V, E) có trọng số, cây khung nhỏ nhất của đồ thị là cây khung có tổng trọng số các cạnh trên cây là nhỏ nhất.

Hình vẽ dưới đây minh họa một cây khung nhỏ nhất trên đồ thị có trọng số:

<center>

</center>

3. Bài toán tìm cây khung nhỏ nhất

Bài toán tìm cây khung nhỏ nhất trên đồ thị được phát biểu như sau: Cho đơn đồ thị GG vô hướng có trọng số gồm nn đỉnh và mm cạnh. Với một cây khung TT của đồ thị, ta gọi trọng số của cây TT là tổng trọng số của các cạnh trên cây. Hãy xác định cây khung có trọng số nhỏ nhất?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương n,mn, m - số đỉnh và số cạnh của đồ thị.
  • mm dòng tiếp theo, mỗi dòng chứa ba số nguyên dương u,v,cu, v, c - thể hiện một cạnh của đồ thị nối hai đỉnh u,vu, v có trọng số là cc.

Ràng buộc:

  • 1n,m1061 \le n, m \le 10^6.
  • 1uvn1 \le u \ne v \le n.
  • 1c1061 \le c \le 10^6.

Output:

  • In ra trọng số của cây khung nhỏ nhất, theo sau đó là các cạnh của cây khung kèm theo trọng số, mỗi cạnh trên một dòng. Còn nếu đồ thị không liên thông thì đưa ra thông báo Unconnected Graph.

Sample Input:

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

Sample Output:

5
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1

Giải thích:

Cây khung của đồ thị được thể hiện ở hình bên dưới:

<center>

</center>

Có hai giải thuật phổ biến để tìm cây khung nhỏ nhất trên đồ thị, và dưới đây chúng ta sẽ cùng phân tích cả hai giải thuật đó.

II. Giải thuật Kruskal (Joseph Kruskal - 1956)

1. Ý tưởng

Giải thuật Kruskal được phát minh vào năm 19561956 bởi nhà khoa học cùng tên người Hoa Kỳ, lấy cấu trúc dữ liệu Disjoint Sets Union làm nền tảng. Ý tưởng sẽ là khởi tạo một cây khung TT rỗng, rồi tuần tự thêm các cạnh vào cây cho tới khi tạo được một cây khung của đồ thị gồm n1n - 1 cạnh. Tuy nhiên, ta sẽ không thêm cạnh theo thứ tự tùy ý, mà sẽ chọn các cạnh lần lượt theo thứ tự tăng dần của trọng số.

Kế tiếp, lần lượt thử thêm các cạnh vào cây TT. Nếu như cạnh (u,v)(u, v) thêm vào cây TT mà không tạo ra chu trình đơn, thì kết nạp cạnh đó vào cây. Cứ làm như vậy cho tới khi:

  • Hoặc đã kết nạp đủ n1n - 1 cạnh vào cây, khi đó ta thu được TT là cây khung nhỏ nhất của đồ thị.
  • Hoặc chưa kết nạp đủ n1n - 1 cạnh vào cây nhưng trong các cạnh còn lại, thêm cạnh nào vào cây cũng tạo ra chu trình đơn. Khi đó đồ thị ban đầu là không liên thông, đồng nghĩa với việc không thể tìm thấy cây khung.

Việc sắp xếp lại các cạnh của đồ thị theo thứ tự tăng dần của trọng số rất đơn giản, chỉ cần sử dụng một danh sách cạnh kiểu bản ghi gồm ba thông số: (u,v,c)(u, v, c) lần lượt là hai đầu mút của cạnh và trọng số của cạnh đó, rồi sắp xếp danh sách đó theo trường cc là xong. Nhưng làm sao để xác định một cạnh khi thêm vào cây có tạo thành chu trình đơn hay không? Nhận xét rằng, tập cạnh trong TT ở các bước sẽ tạo thành một rừng các cây phân biệt (đồ thị không có chu trình đơn). Muốn thêm một cạnh (u,v)(u,v) vào rừng TT mà không tạo thành chu trình đơn thì cạnh đó phải nối hai cây khác nhau trong TT (nếu nối giữa hai đỉnh trong cùng một cây thì sẽ tạo thành chu trình đơn trong cây đó). Áp dụng cấu trúc dữ liệu DSU, ta có một cách nhanh để xây dựng giải thuật Kruskal:

  • Xét cạnh (u,v),(u,v), xác định gốc của hai đỉnh uuvvr1r_1r2r_2.

  • Nếu r1=r2,r_1=r_2, tức là uuvv thuộc chung một cây, việc thêm cạnh (u,v)(u,v) vào TT sẽ tạo ra chu trình đơn. Trường hợp này ta không thu nhận cạnh (u,v)(u,v) vào cây khung.

  • Nếu r1r2,r1≠r2, tức là uuvv thuộc hai cây khác nhau, ta hợp nhất hai cây gốc r1r_1r2,r_2, thêm cạnh (u,v)(u,v) vào cây khung.

    <center>

    Hợp nhất hai cây gốc r1r_1 và r2r_2

    </center>
  • Nếu số lượng cạnh của TT đã đủ n1,n-1, dừng thuật toán và đưa ra cây khung tương ứng. Ngược lại nếu đã duyệt hết các cạnh của đồ thị mà vẫn không chọn đủ n1n-1 cạnh vào T,T, trường hợp này đồ thị không liên thông, việc tìm kiếm cây khung thất bại.

2. Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int u, v, c;
};

void enter(int &n, int &m, vector < Edge> &edges)
{
    cin >> n >> m;

    edges.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
}

// Hàm so sánh để sắp xếp lại cạnh của đồ thị theo trọng số.
bool cmp(Edge a, Edge b)
{
    return a.c < b.c;
}

// Tìm gốc của đỉnh u.
int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

// Hợp nhất hai cây con gốc r1 và r2.
void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

void kruskal(int n, int m, vector < Edge > &edges)
{
    // Khởi tạo rừng các cây ban đầu gồm n đỉnh phân biệt, coi như n cây.
    // Ban đầu gốc của các cây là chính nó, khởi tạo bằng -1 theo DSU.
    vector < int > lab(n + 1, -1);
    // Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần về trọng số.
    sort(edges.begin(), edges.end(), cmp);

    int mst_weight = 0;
    vector < Edge > mst_edges;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        // Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        // Hợp nhất hai cây chứa hai đỉnh u và v.
        if (r1 != r2)
        {
            union_trees(r1, r2, lab);
            mst_weight += edges[i].c;
            mst_edges.push_back(edges[i]);
        }

        // Đã kết nạp đủ n - 1 cạnh, dừng thuật toán.
        if (mst_edges.size() == n - 1)
            break;
    }

    // Kết luận có tìm được cây khung hay không và đưa ra cây khung nếu có.
    if (mst_edges.size() != n - 1)
        cout << "Unconnected Graph";
    else 
    {
        cout << mst_weight << endl;
        for (auto e: mst_edges)
            cout << e.u << ' ' << e.v << ' ' << e.c << endl;
    }
}

main()
{
    int n, m;
    vector < Edge > edges;

    enter(n, m, edges);
    kruskal(n, m, edges);

    return 0;
}

Ngôn ngữ Python:

# Tìm gốc của đỉnh u.
def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


# Hợp nhất hai cây con gốc r1 và r2.
def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


# Hàm so sánh để sắp xếp lại cạnh của đồ thị theo trọng số.
def take_weight(element):
    return element[2]


def kruskal(n, m, edges):
    # Khởi tạo rừng các cây ban đầu gồm n đỉnh phân biệt, coi như n cây.
    # Ban đầu gốc của các cây là chính nó, khởi tạo bằng -1 theo DSU.
    lab = [-1] * (n + 1)
    # Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần về trọng số.
    edges = sorted(edges, key=take_weight)

    mst_weight = 0
    mst_edges = []
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        # Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        # Hợp nhất hai cây chứa hai đỉnh u và v.
        if r1 != r2:
            union_trees(r1, r2, lab)
            mst_weight += edges[i][2]
            mst_edges.append(edges[i])
        
        if len(mst_edges) == n - 1:
            break

    # Kết luận có tìm được cây khung hay không và đưa ra cây khung nếu có.
    if len(mst_edges) != n - 1:
        print('Unconnected Graph')
    else:
        print(mst_weight)
        for (u, v, c) in mst_edges:
            print(u, v, c)


if __name__ == '__main__':
    n, m = map(int, input().split())
    
    edges = []
    for _ in range(m):
        u, v, c = map(int, input().split())
        edges.append((u, v, c))

    kruskal(n, m, edges)

III. Giải thuật Prim (Robert Prim - 1957)

1. Ý tưởng

Trong trường hợp đồ thị dày (có nhiều cạnh), thì giải thuật Kruskal sẽ hoạt động hơi chậm (bởi vì bắt buộc phải sắp xếp lại các cạnh trước khi thực hiện giải thuật). Nhà khoa học Robert C. Prim đã phát triển hoàn chỉnh thuật toán Prim vào năm 1957,1957, cho phép tìm kiếm cây khung nhỏ nhất của đồ thị một cách hiệu quả trong trường hợp đồ thị dày và có số đỉnh vừa phải.

Giải thuật có thể phát biểu như sau: Trên đơn đồ thị vô hướng G=(V,E)G=(V,E)nn đỉnh, quy ước wu,vw_{u,v} là trọng số cạnh (u,v)(u,v). Xét cây TT trong GG và một đỉnh vv bất kỳ, gọi khoảng cách từ vv tới TT là trọng số nhỏ nhất trong số các cạnh nối trực tiếp của vv với một đỉnh nào đó trong TT:

d[v]=minwu,vuTd[v]=\text{min}{w_{u,v} | u \in T}

Ban đầu ta khởi tạo cây TT chỉ gồm đỉnh {1}\{1\}. Sau đó, cứ chọn trong số các đỉnh không thuộc TT một đỉnh uu gần TT nhất, kết nạp đỉnh đó vào T,T, đồng thời kết nạp luôn cạnh nối tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi:

  • Hoặc đã kết nạp được nn đỉnh thì ta có TT chính là cây khung nhỏ nhất.
  • Hoặc chưa kết nạp được hết nn đỉnh, nhưng đã xét hết cạnh của đồ thị. Khi đó đồ thị đã cho không liên thông, việc tìm cây khung thất bại.

Về kĩ thuật cài đặt, ban đầu gán d[1]=1d[1]=1d[u]=;u1d[u]=\infty; \forall u≠1. Tại mỗi bước chọn đỉnh, ta tìm đỉnh uu không thuộc TTd[u]d[u] nhỏ nhất. Khi kết nạp uu vào T,T, cập nhật lại khoảng cách từ các đỉnh còn lại tới cây TT:

<center>

d[v]=min(d[v],wu,v),d[v]=\text{min}\big(d[v],w_{u,v}\big), với vv là các đỉnh kề với uu.

</center>

Sử dụng một mảng lưu vết, gán trace[v]=utrace[v]=u khi tìm được đỉnh vv gần TT nhất ở mỗi bước kết nạp, mục đích lưu lại đỉnh uu thuộc TT nối với vv đã tạo ra khoảng cách gần nhất đó, sau này ta sẽ sử dụng để truy vết. Nếu số lượng đỉnh của đồ thị không nhiều, ta có thể sử dụng ma trận kề để biểu diễn, và thuật toán khi đó có độ phức tạp O(n2)O(n^2).

Việc tìm ra đỉnh uu gần TT nhất (có d[u]d[u] nhỏ nhất) có thể được cải tiến bằng cách sử dụng Heap (trong C++/Python đã được cài đặt sẵn bằng hàng đợi ưu tiên) cùng với danh sách kề để biểu diễn đồ thị. Tuy nhiên, thông thường trên đồ thị có số cạnh vừa phải, người ta sẽ sử dụng giải thuật Kruskal thay vì dùng Prim Heap.

Khi đó, độ phức tạp giải thuật sẽ là: O((n+m)×log(n))O\big((n + m) \times \log(n)\big).

3. Cài đặt

Cài đặt cơ bản không sử dụng Heap

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

const int INFTY = 2e6;

// Nhập đồ thị, lưu trọng số các cạnh bằng một ma trận kề.
// Cách làm phù hợp với đồ thị có số đỉnh khoảng 5000 trở xuống.
void enter(int &n, int &m, vector < vector < int > > &weight)
{
    cin >> n >> m;

    weight = vector < vector < int > >(n + 1, vector < int >(n + 1));
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v <= n; ++v)
            weight[u][v] = (u == v) ? 0 : INFTY;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v >> weight[u][v];

        weight[v][u] = weight[u][v];
    }
}

// Giải thuật Prim chưa cải tiến bước tìm đỉnh u có d[u] nhỏ nhất.
void basic_prim(int n, int m, vector < vector < int > > &weight)
{
    vector < int > d(n + 1, INFTY);
    vector < bool > is_free(n + 1, true);
    vector < int > trace(n + 1);
    is_free[1] = false;
    d[1] = 0;

    for (int i = 1; i <= n; ++i)
    {
        // Tìm đỉnh u chưa bị kết nạp vào cây khung có d[u] nhỏ nhất.
        int u = 0, flag = INFTY;
        for (int v = 1; v <= n; ++v)
            if (is_free[v] && d[v] < flag)
            {
                flag = d[v];
                u = v;
            }

        // Nếu không tìm được u thì đồ thị không liên thông, việc tìm
        // cây khung thất bại và ta dừng thuật toán tại đây.
        if (u == 0)
        {
            cout << "Unconnected Graph";
            return;
        }

        // Kết nạp u vào cây khung nếu tìm thấy u, đánh dấu nó đã kết nạp.
        is_free[u] = false;

        // Duyệt các đỉnh v kề u và chưa được kết nạp vào cây.
        // Tối ưu các khoảng cách d[v] bằng trọng số cạnh (u, v).
        for (int v = 1; v <= n; ++v)
            if (is_free[v] && d[v] > weight[u][v])
            {
                // Cập nhật lại d[v] nhỏ nhất, đồng thời lưu vết đỉnh 
                // nối với v tạo khoảng cách ngắn nhất tới cây T là u.
                d[v] = weight[u][v];
                trace[v] = u;
            }
    }

    // Truy vết và in ra cây khung tìm được.
    long long mst_weight = 0;
    vector < pair < int, int > > mst_edges;
    for (int v = 2; v <= n; ++v)
    {
        mst_edges.push_back({trace[v], v});
        mst_weight += weight[trace[v]][v];
    }

    cout << mst_weight << endl;
    for (auto e: mst_edges)
        cout << e.first << ' ' << e.second << ' ' << weight[e.first][e.second] << endl;
}

main()
{
    int n, m;
    vector < vector < int > > weight;

    enter(n, m, weight);
    basic_prim(n, m, weight);

    return 0;
}

Ngôn ngữ Python:

INFTY = 2 * (10 ** 6)


def basic_prim(n, m, weight):
    d = [INFTY] * (n + 1)
    is_free = [True] * (n + 1)
    trace = [0] * (n + 1)
    is_free[1], d[1] = False, 0

    for i in range(n):
        # Tìm đỉnh u chưa bị kết nạp vào cây khung có d[u] nhỏ nhất.
        u = 0, flag = INFTY
        for v in range(1, n + 1):
            if is_free[v] and flag > d[v]:
                flag = d[v]
                u = v

        # Nếu không tìm được u thì đồ thị không liên thông, việc tìm
        # cây khung thất bại và ta dừng thuật toán tại đây.
        if u == 0:
            print('Unconnected Graph')
            return

        # Kết nạp u vào cây khung nếu tìm thấy u, đánh dấu nó đã kết nạp.
        is_free[u] = False

        # Duyệt các đỉnh v kề u và chưa được kết nạp vào cây.
        # Tối ưu các khoảng cách d[v] bằng trọng số cạnh (u, v).
        for v in range(1, n + 1):
            if is_free[v] and d[v] > weight[u][v]:
                # Cập nhật lại d[v] nhỏ nhất, đồng thời lưu vết đỉnh 
                # nối với v tạo khoảng cách ngắn nhất tới cây T là u.
                d[v] = weight[u][v]
                trace[v] = u

    # Truy vết và in ra cây khung tìm được.
    mst_weight = 0
    mst_edges = []
    for v in range(2, n + 1):
        mst_edges.append((trace[v], v, weight[trace[v]][v]))
        mst_weight += weight[trace[v]][v]

    print(mst_weight)
    for (u, v, c) in mst_edges:
        print(u, v, c)


if __name__ == '__main__':
    # Nhập đồ thị, lưu trọng số các cạnh bằng một ma trận kề.
    # Cách làm phù hợp với đồ thị có số đỉnh khoảng 5000 trở xuống.
    n, m = map(int, input().split())

    weight = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            weight[u][v] = 0 if u == v else INFTY

    for i in range(m):
        u, v, c = map(int, input().split())
        weight[u][v] = weight[v][u] = c

    basic_prim(n, m, weight)

Cải tiến bằng hàng đợi ưu tiên

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

// Định danh lại kiểu pair < int, int > để viết cho ngắn gọn.
typedef pair < int, int > II;

const MAX_WEIGHT = 2e6;

// Nhập dữ liệu đồ thị, sử dụng danh sách kề để cải tiến thuật toán.
// Cách làm phù hợp với đồ thị có số đỉnh khoảng 10^6.
void enter(int &n, int &m, vector < vector < II > > &adj)
{
    cin >> n >> m;

    // Danh sách kề adj[u]: Lưu các đỉnh kề của u kèm theo trọng số cạnh.
    adj.resize(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;

        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
}

void prim_heap(int n, int m, vector < vector < II > > &adj)
{
    // Hàng đợi ưu tiên lưu các cặp giá trị (d[u], u). 
    // Cặp nào có d[u] nhỏ nhất tự động được đẩy lên top của hàng đợi.
    priority_queue < II, vector < II >, greater < II > > qu_min;
    vector < int > d(n + 1, MAX_WEIGHT);
    vector < bool > is_free(n + 1, true);
    vector < II > trace(n + 1);
    d[1] = 0;
    is_free[1] = false;
    qu_min.push({d[1], 1});

    int mst_vertexes = 0;
    while (!qu_min.empty())
    {
        int cur_dis = qu_min.top().first;
        int u = qu_min.top().second();
        qu_min.pop();

        // Đỉnh u đã được kết nạp vào cây khung rồi thì không sử dụng lại
        // nhãn d[u] nữa, bỏ qua nó luôn.
        if (d[u] != cur_dis)
            continue;

        // Kết nạp u vào cây khung và tăng số đỉnh của cây khung lên 1.
        is_free[u] = false;
        ++mst_vertexes;

        // Tối ưu nhãn d[v] của các đỉnh v kề với u, đỉnh nào tối ưu được
        // thì đưa nó vào trong hàng đợi ưu tiên và lưu vết luôn. Tuy nhiên,
        // khi lưu vết cần lưu cả đỉnh nối với v trên cây và trọng số cạnh nối.
        for (auto e: adj[u])
        {
            int v = e.first, w = e.second;
            if (is_free[v] && d[v] > w)
            {
                d[v] = w;
                trace[v] = {u, w};
                qu_min.push({d[v], v});
            }
        }
    }

    // Nếu cây T không có đủ n đỉnh thì đồ thị không liên thông, việc
    // tìm cây khung thất bại.
    if (mst_vertexes < n)
    {
        cout << "Unconnected Graph";
        return;
    }

    // Truy vết và in ra cây khung tìm được.
    long long mst_weight = 0;
    vector < pair < II , int > > mst_edges;
    for (int v = 2; v <= n; ++v)
    {
        mst_edges.push_back({{trace[v].first, v}, trace[v].second});
        mst_weight += trace[v].second;
    }

    cout << mst_weight << endl;
    for (auto e: mst_edges)
        cout << e.first.first << ' ' << e.first.second << ' ' << e.second << endl; 
}

main()
{
    int n, m;
    vector < vector < int > > adj;

    enter(n, m, adj);
    prim_heap(n, m, adj);

    return 0;
}

Ngôn ngữ Python:

from queue import PriorityQueue


def prim_heap(n, m, adj):
    # Hàng đợi ưu tiên lưu các cặp giá trị (d[u], u). 
    # Cặp nào có d[u] nhỏ nhất tự động được đẩy lên top của hàng đợi.
    qu_min = PriorityQueue()
    

if __name__ == '__main__':
    # Nhập dữ liệu đồ thị, sử dụng danh sách kề để cải tiến thuật toán.
    # Cách làm phù hợp với đồ thị có số đỉnh khoảng 10^6.
    n, m = map(int, input().split())

    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, c = map(int, input().split())
        adj[u].append((v, c))
        adj[v].append((u, c))

    prim_heap(n, m, adj)

IV. Bài toán minh họa

1. Ô tô điện

Đề bài

Hiện nay, nhiều hãng xe đang phát triển xe ô tô chạy năng lượng điện thay vì chạy bằng xăng, dầu. Tuy nhiên, ắc quy cấp điện dùng cho những mẫu xe điện này còn rất nặng nề và tốn kém, vì vậy các nhà thiết kế luôn phải xác định trước được dung lượng ắc quy và phạm vi di chuyển tối đa của chiếc xe này.

Mạng lưới giao thông đường bộ gồm nn thành phố (các thành phố đánh số từ 00 tới n1n-1) được nối với nhau bằng mm con đường hai chiều. Mỗi thành phố có một trạm nạp điện cho ắc quy xe. Dọc theo tuyến đường giữa hai thành phố, chiếc xe có thể đi qua một số các thành phố tùy ý khác, nhưng khoảng cách giữa các cặp thành phố liên tiếp dọc theo tuyến đường không được dài hơn phạm vi di chuyển quy định của chiếc xe.

Hãy xác định phạm vi di chuyển tối thiểu mà chiếc xe cần đáp ứng (quãng đường tối thiểu mà xe di chuyển được từ lúc nạp điện tới lúc hết điện) để chiếc xe có thể đi lại giữa hai thành phố bất kỳ mà không bị hết điện trước khi tới được một trạm nạp điện?

Input:

  • Gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu gồm:

    • Dòng đầu tiên chứa hai số nguyên dương nnmm – số lượng thành phố và số tuyến đường giao thông.
    • mm dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm u,v,wu,v,w – cho biết có con đường hai chiều nối giữa thành phố uu và thành phố vv với khoảng cách là ww.
  • Kết thúc của file dữ liệu là một dòng gồm hai chữ số 0,0, cho biết đã kết thúc dữ liệu vào (không cần xử lý).

Ràng buộc:

  • 1n,m1061 \le n, m \le 10^6.
  • 0uv<n0 \le u \ne v < n.
  • 0w1060 \le w \le 10^6.

Output:

  • Ứng với mỗi bộ dữ liệu, in ra một số nguyên là phạm vi di chuyển tối thiểu chiếc xe cần đáp ứng để nó có thể di chuyển qua lại giữa hai thành phố bất kỳ. Nếu không thể tìm được đáp số thì đưa ra thông báo IMPOSSIBLE.

Sample Input:

3 3
0 1 3
1 2 4
2 1 5
3 1
0 1 3
0 0

Sample Output:

4
IMPOSSIBLE

Ý tưởng

Đề bài có thể phát biểu lại thành: Tìm một hành trình để xe điện đi qua mọi địa điểm, sao cho khoảng cách lớn nhất giữa hai địa điểm liên tiếp là bé nhất.

Vậy ý tưởng là tìm cây khung nhỏ nhất của đồ thị, cạnh cuối cùng được kết nạp vào cây khung sẽ là kết quả. Các bạn có thể sử dụng giải thuật Kruskal hoặc Prim đều được. Solution mẫu sẽ sử dụng giải thuật Kruskal.

Độ phức tạp: O(n×log(n))O\big(n \times \log(n)\big).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

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

int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

void kruskal(int n, int m, vector < Edge > &edges)
{
    vector < int > &lab(n + 1, -1);
    sort(edges.begin(), edges.end(), cmp);

    int minimum_range = 0, mst_edges = 0;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        if (r1 != r2)
        {
            union_trees(r1, r2, lab);

            minimum_range = edges[i].w;
            ++mst_edges;
        }

        if (mst_edges == n - 1)
            break;
    }

    if (mst_edges != n - 1)
        cout << "IMPOSSIBLE" << endl;
    else 
        cout << minimum_range << endl;
}

main()
{
    while (true)
    {
        int n, m;
        cin >> n >> m;

        if (n == 0 && m == 0)
            break;
        
        vector < Edge > edges;
        
        edges.resize(m);
        for (int i = 0; i < m; ++i)
            cin >> edges[i].u >> edges[i].v >> edges[i].w;

        kruskal(n, m, edges);
    }
}

Ngôn ngữ Python:

def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


def take_weight(element):
    return element[2]


def kruskal(n, m, edges):
    lab = [-1] * (n + 1)
    edges = sorted(edges, key=take_weight)

    minimum_range, mst_edges = 0, 0
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        # Thêm cạnh (u, v) vào đồ thị nếu cạnh này không tạo ra chu trình đơn.
        # Hợp nhất hai cây chứa hai đỉnh u và v.
        if r1 != r2:
            union_trees(r1, r2, lab)
            
            minimum_range = edges[i][2]
            mst_edges += 1
        
        if mst_edges == n - 1:
            break

    if mst_edges != n - 1:
        print('IMPOSSIBLE')
    else:
        print(mst_edges)


if __name__ == '__main__':
    while True:
        n, m = map(int, input().split())

        if n == 0 and m == 0:
            break

        edges = []
        for _ in range(m):
            u, v, c = map(int, input().split())
            edges.append((u, v, c))

        kruskal(n, m, edges)

2. Động viên đàn bò

Đề bài

Một trang trại gồm nn cánh đồng và mm con đường nối hai chiều giữa một số cặp cánh đồng, mỗi cánh đồng là nơi ở của một chú bò. Do đã già nua nên chủ trang trại rất mệt mỏi với việc phải đi lại trên quá nhiều con đường, vì vậy bác ta quyết định loại bỏ một số con đường, sao cho các cánh đồng vẫn liên thông với nhau.

Biết được thông tin này, đàn bò rất buồn bã. Người con trai của chủ trang trại sẽ phải thay bố mình đi thăm mỗi chú bò ít nhất một lần trong ngày để động viên chúng. Mỗi lần đi qua cánh đồng i,i, anh phải trò chuyện với chú bò ở đó trong thời gian cic_i để giúp chú bò phấn chấn trở lại (dù chỉ là đi ngang qua cánh đồng đó).

Để thuận tiện cho công việc vào sáng hôm sau, người con trai quyết định sẽ chọn một cánh đồng nào đó để xuất phát từ đó, đi thăm tất cả các chú bò và quay trở lại cánh đồng đó để nghỉ đêm. Dĩ nhiên, khi quay trở về vào buổi tối, anh ta sẽ lại trò chuyện với chú bò ở cánh đồng mình nghỉ đêm thêm một lần nữa.

Hãy xác định tổng thời gian nhỏ nhất mà người con trai cần để đi thăm tất cả đàn bò trong một ngày?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương nnmm – số lượng cánh đồng và số đường đi giữa chúng.
  • nn dòng tiếp theo, dòng thứ ii chứa số nguyên dương cic_i – thời gian cần trò chuyện với chú bò ở cánh đồng ii.
  • mm dòng cuối cùng, mỗi dòng ghi ba số nguyên dương u,v,tu,v,t – thể hiện con đường hai chiều nối giữa cánh đồng uu và cánh đồng vv cần thời gian tt để di chuyển. Không có hai cánh đồng nào được nối bởi nhiều hơn 11 con đường.

Ràng buộc:

  • 1n1041≤n≤10^4.
  • 1m1051≤m≤10^5.
  • 1ci103;i:1in1≤c_i≤10^3; \forall i: 1 \le i \le n.
  • 1t1031 \le t \le 10^3.

Output:

  • Một số nguyên duy nhất là tổng thời gian tối thiểu để đi thăm tất cả đàn bò trong một ngày.

Sample Input:

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Sample Output:

176

Ý tưởng

Nhận xét: Đề bài có thể tóm tắt lại thành: Tìm một hành trình gồm (n1)(n - 1) cạnh, xuất phát từ 11 đỉnh bất kỳ đi qua tất cả các đỉnh còn lại và quay trở về đỉnh xuất phát. Như vậy bài toán trở thành tìm cây khung nhỏ nhất, tuy nhiên trọng số cạnh sẽ được xử lý lại.

Xét cạnh (u,v)(u, v): Nếu đi qua cạnh này, thì sẽ tốn tổng thời gian là 2×w(u,v)+cu+cv,2 \times w(u, v) + c_u + c_v, bao gồm thời gian đi và về cộng với thời gian nói chuyện cùng chú bò ở cánh đồng uu và cánh đồng vv. Ta tạo lại trọng số cho các cạnh theo công thức trên, sau đó tìm cây khung nhỏ nhất trên đồ thị.

Cuối cùng, chọn đỉnh xuất phát sscsc_s nhỏ nhất và cộng thêm csc_s vào kết quả, do cánh đồng xuất phát sẽ trở về thêm một lần nữa. Thực tế điều này có được từ việc tính tổng mọi đường đi trên cây tạo thành (mỗi đường đi bằng các cạnh + số ở các đỉnh) sau đó nhân với 22 và cộng thêm đỉnh gốc có giá trị cc nhỏ nhất.

Độ phức tạp: O(m×log(m))O\big(m \times \log(m)\big).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

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

void enter(int &n, int &m, vector < int > &c, vector < Edge > &edges)
{
    cin >> n >> m;

    c.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    edges.resize(m);
    for (int i = 0; i < m; ++i)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].w = 2 * edges[i].w + c[edges[i].u] + c[edges[i].v];
}

int find_root(int u, vector < int > &lab)
{
    return (lab[u] < 0) ? u : lab[u] = find_root(lab[u], lab);
}

void union_trees(int r1, int r2, vector < int > &lab)
{
    int child_r1 = -lab[r1], child_r2 = -lab[r2];

    if (child_r1 < child_r2)
        swap(r1, r2);

    lab[r1] += lab[r2];
    lab[r2] = r1;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

void kruskal(int n, int m, vector < int > &c, vector < Edge > &edges)
{
    vector < int > lab(n + 1, -1);
    sort(edges.begin(), edges.end(), cmp);

    int res = *min_element(c.begin() + 1, c.end());
    int mst_edges = 0;
    for (int i = 0; i < m; ++i)
    {
        int r1 = find_root(edges[i].u), r2 = find_root(edges[i].v);

        if (r1 != r2)
        {
            union_trees(r1, r2, lab);

            res += edges[i].w;
            ++mst_edges;
        }

        if (mst_edges == n - 1)
            break;
    }

    cout << mst_edges;
}

main()
{
    int n, m;
    vector < int > c;
    vector < Edge > edges;

    enter(n, m, edges);
    kruskal(n, m, edges);

    return 0;
}

Ngôn ngữ Python:

def find_root(u, lab):
    if lab[u] < 0:
        return u
    else:
        lab[u] = find_root(lab[u], lab)
        return lab[u]


def union_trees(r1, r2, lab):
    child_r1, child_r2 = -lab[r1], -lab[r2]

    if child_r1 < child_r2:
        r1, r2 = r2, r1

    lab[r1] += lab[r2]
    lab[r2] = r1


def take_weight(element):
    return element[2]


def kruskal(n, m, c, edges):
    lab = [-1] * (n + 1)
    edges = sorted(edges, key=take_weight)

    res = min(c)
    mst_edges = 0
    for i in range(m):
        r1, r2 = find_root(edges[i][0], lab), find_root(edges[i][1], lab)

        if r1 != r2:
            union_trees(r1, r2, lab)
            
            res += edges[i][2]
            mst_edges += 1
        
        if mst_edges == n - 1:
            break

    print(res)


if __name__ == '__main__':
    n, m = map(int, input().split())

    c = [0] + [int(x) for x in input().split()]

    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    kruskal(n, m, c, edges)

Các bạn có thể tham khảo thêm bài tập tự luyện tại <i>đây.</i>

V. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.