Một công ty máy tính cần nối mạng máy tính lại với nhau. Có phương án nối cáp hai chiều giữa các cặp máy tính, mỗi phương án có một chi phí khác nhau. Hãy tìm cách nối mạng sao cho tất cả các máy tính đều được kết nối (trực tiếp hoặc gián tiếp) và tổng chi phí là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và .
dòng tiếp theo, mỗi dòng chứa ba số nguyên cho biết có thể nối máy và với chi phí là .
Kết quả: Một số nguyên duy nhất là tổng chi phí nhỏ nhất để kết nối tất cả các máy tính.
Ví dụ:Dữ liệu:
5 7
1 2 2
1 4 5
1 5 4
2 3 3
2 5 2
3 4 1
4 5 3
Kết quả:
8
Giải thích:
Đây là bài toán tìm cây khung nhỏ nhất của đồ thị. Một phương án tối ưu là chọn các cạnh chi phí , chi phí , chi phí , và chi phí . Tổng chi phí là .
