fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm> // Hàm sort
  4. using namespace std;
  5.  
  6. // Cấu trúc để lưu cạnh đồ thị,
  7. // u, v là 2 đỉnh, w là trọng số cạnh
  8. struct edge {
  9. int u, v, w;
  10. };
  11. // Hàm so sánh để dùng trong hàm sort ở dưới
  12. bool cmp(const edge &a, const edge &b) {
  13. return a.w < b.w;
  14. }
  15.  
  16. // Số đỉnh tối đa trong đề bài
  17. #define N 10005
  18.  
  19. // 2 mảng sử dụng trong Disjoint Set
  20. int cha[N], hang[N];
  21.  
  22. // Tìm xem u thuộc cây nào
  23. int find(int u) {
  24. if (cha[u] != u) cha[u] = find(cha[u]);
  25. return cha[u];
  26. }
  27.  
  28. // Hợp nhất 2 cây chứ u và v,
  29. // Trả về false nếu không thể hợp nhất
  30. bool join(int u, int v) {
  31. u = find(u); v = find(v);
  32. if (u == v) return false;
  33. if (hang[u] == hang[v]) hang[u]++;
  34. if (hang[u] < hang[v]) cha[u] = v;
  35. else cha[v]=u;
  36. return true;
  37. }
  38.  
  39. int main() {
  40. // Thêm dòng này để cin, cout chạy nhanh
  41. ios::sync_with_stdio(false); cin.tie(0);
  42.  
  43. // Nhập vào số đỉnh và số cạnh
  44. int n, m; cin >> n >> m;
  45.  
  46. // Nhập danh sách các cạnh
  47. vector<edge> edges(m);
  48. for (edge &e: edges) cin >> e.u >> e.v >> e.w;
  49.  
  50. // Sắp xếp lại các cạnh theo trọng số tăng dần
  51. sort(edges.begin(), edges.end(), cmp);
  52.  
  53. // Khởi tạo cấu trúc Disjoint Set
  54. for (int i=1; i<=n; i++) {
  55. cha[i] = i;
  56. hang[i] = 0;
  57. }
  58.  
  59. // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất
  60. int mst_weight = 0;
  61.  
  62. // Duyệt qua các cạnh theo thứ tự đã sắp xếp
  63. for (edge &e: edges) {
  64. // Thử hợp nhất 2 cây chứa u và v
  65. if (join(e.u, e.v)) {
  66. // Hợp nhất thành công, ta thêm e và kết quả
  67. mst_weight += e.w;
  68. }
  69. }
  70.  
  71. // Xuất kết quả
  72. cout << mst_weight;
  73. return 0;
  74. }
Runtime error #stdin #stdout 0s 4400KB
stdin
Standard input is empty
stdout
Standard output is empty