Cây khung nhỏ nhất (MST) của đồ thị vô hướng liên thông có trọng số là cây nối tất cả đỉnh với tổng trọng số cạnh nhỏ nhất. Thuật toán Kruskal sắp xếp cạnh theo trọng số tăng dần rồi lần lượt thêm cạnh không tạo chu trình (dùng cấu trúc Union-Find).
Hãy in tổng trọng số cây khung nhỏ nhất.
Dòng đầu n m. m dòng u v w — cạnh vô hướng trọng số w. Đồ thị liên thông.
1 <= n <= 1000; n-1 <= m <= 5000; 1 <= w <= 10^6.
Một số nguyên: tổng trọng số cây khung nhỏ nhất.
Ví dụ:
Đầu vào:
4 5
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
Đầu ra:
6
Giải thích:
Đang tải editor...