Untitled
plain_text
a month ago
1.8 kB
1
Indexable
Never
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N = 10005; // Cấu trúc để lưu cạnh đồ thị // u và v là 2 đỉnh, w là trọng số struct edge { int u, v, w; }; // Hàm so sánh để dùng trong hàm sort ở dưới bool cmp(const edge& a, const edge& b) { return a.w > b.w; } // 2 mảng sử dụng trong Disjoint Set int cha[1005], hang[1005]; // Tìm xem u thuộc cây nào int find(int u) { if (cha[u] != u) { cha[u] = find(cha[u]); } return cha[u]; } // Hợp nhất 2 cây chứa u và v, // Trả về false nếu không thể hợp nhất bool join(int u, int v) { u = find(u); v = find(v); if (u == v) return false; if (hang[u] == hang[v]) hang[u]++; if (hang[u] < hang[v]) cha[u] = v; else cha[v] = u; return true; } int main() { int n, m; cin >> n >> m; // Nhập danh sách các cạnh vector<edge> edges(m); for (edge& e : edges) { cin >> e.u >> e.v >> e.w; } // Sắp xếp lại các cạnh theo tọng số tăng dần sort(edges.begin(), edges.end(), cmp); cout << endl; for (edge& e : edges) { cout << e.u << " " << e.v << " " << e.w << endl; } // Khởi tạo cấu trúc Disjoint Set for (int i = 1; i <= n; i++) { cha[i] = i; hang[i] = 0; } // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất int mst_weight = 0; // Duyệt qua các cạnh theo thứ tự đã sắp xếp for (edge &e : edges) { // Thử hợp nhất 2 cây chứ u và v if (join(e.u, e.v)) { // Hợp nhất thành công, ta thêm e và kết quả mst_weight += e.w; cout << e.u << " " << e.v << endl; } } cout << mst_weight; }