Cây Khung Nhỏ Nhất (Kruskal & Disjoint Set Union)
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng liên thông gồm N đỉnh (1..N) và M cạnh có trọng số. Hãy tìm tổng trọng số của Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST) nối toàn bộ N đỉnh.
Dữ liệu vào (Input)
- Dòng 1: Hai số nguyên
NvàM(1 ≤ N ≤ 10^5,N - 1 ≤ M ≤ 2 × 10^5). Mdòng tiếp theo: Mỗi dòng gồm 3 số nguyênu v w(1 ≤ w ≤ 10^9).
Dữ liệu ra (Output)
- In ra tổng trọng số nhỏ nhất của cây khung.
Ví dụ mẫu
Sample Input 1
4 5
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3
Sample Output 1
6
Community Discussion