Ý tưởng giải bài toán:

1. Nhận xét:

   • Bài toán yêu cầu tìm Cây khung nhỏ nhất (Minimum Spanning Tree - MST) trong một đồ thị.
   • Sử dụng thuật toán Kruskal hoặc Prim để giải bài toán này.

2. Thuật toán Kruskal:

   • Bước 1: Sắp xếp các cạnh theo chi phí sửa chữa tăng dần.
   • Bước 2: Duyệt qua các cạnh:
     • Thêm cạnh vào MST nếu nó không tạo thành chu trình (sử dụng Union-Find để kiểm tra chu trình).
   • Bước 3: Dừng khi MST có đủ ~n-1~ cạnh hoặc không thể kết nối tất cả các thành phố.

3. Kiểm tra điều kiện không thể kết nối:

   • Nếu sau khi duyệt tất cả các cạnh mà MST không chứa đủ ~n-1~ cạnh, in "IMPOSSIBLE".

Chương trình C++:

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

struct Edge {
    int u, v;
    long long cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

vector<int> parent, rank;

int find(int u) {
    if (u != parent[u]) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}

bool unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return false;
    if (rank[u] < rank[v]) swap(u, v);
    parent[v] = u;
    if (rank[u] == rank[v]) rank[u]++;
    return true;
}

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

    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    // Sắp xếp các cạnh theo chi phí tăng dần
    sort(edges.begin(), edges.end());

    // Khởi tạo Union-Find
    parent.resize(n + 1);
    rank.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    long long total_cost = 0;
    int count = 0;

    // Duyệt qua các cạnh để xây dựng MST
    for (const auto& edge : edges) {
        if (unite(edge.u, edge.v)) {
            total_cost += edge.cost;
            count++;
            if (count == n - 1) break; // Đủ ~n-1~ cạnh
        }
    }

    // Kiểm tra nếu không thể kết nối tất cả các thành phố
    if (count != n - 1) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << total_cost << endl;
    }

    return 0;
}

Giải thích chương trình:

1. Cấu trúc dữ liệu cạnh (Edge):

   • Gồm ba thành phần: hai đỉnh ~u, v~ và chi phí ~cost~.
   • Định nghĩa toán tử < để sắp xếp các cạnh theo chi phí tăng dần.

2. Union-Find:

   • find(u): Tìm đại diện của tập chứa ~u~.
   • unite(u, v): Hợp nhất hai tập chứa ~u~ và ~v~. Trả về false nếu ~u~ và ~v~ đã cùng một tập.

3. Thuật toán Kruskal:

   • Sắp xếp các cạnh theo chi phí tăng dần.
   • Thêm các cạnh vào MST nếu không tạo thành chu trình.
   • Dừng lại khi MST có đủ ~n-1~ cạnh.

4. Kiểm tra kết quả:

   • Nếu số cạnh trong MST khác ~n-1~, in "IMPOSSIBLE".
   • Ngược lại, in tổng chi phí của MST.

Độ phức tạp:

• Thời gian:
  • Sắp xếp các cạnh: ~O(m \log m)~.
  • Duyệt qua các cạnh và Union-Find: ~O(m \cdot \alpha(n))~, với ~\alpha(n)~ là hàm Ackermann nghịch đảo, rất nhỏ.
  • Tổng: ~O(m \log m)~, vì ~m \geq n~.
• Bộ nhớ:
  • ~O(n + m)~, để lưu các cạnh và cấu trúc Union-Find.

Ví dụ chạy chương trình:

Input:

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

Output:

14

Giải thích:

• Các cạnh được chọn trong MST: ~(2, 4), (1, 2), (5, 4), (2, 3)~.
• Tổng chi phí: ~2 + 3 + 4 + 5 = 14~.

Input:

4 2
1 2 5
3 4 7

Output:

IMPOSSIBLE

Giải thích:

• Không thể kết nối tất cả các thành phố do không đủ cạnh.

Chương trình trên đáp ứng đầy đủ yêu cầu bài toán với các giới hạn ~n, m \leq 10^5~.