Mô tả và yêu cầu

Nâng cấp mạng (VOI 2011)

Một hế thống gồm 𝑛 máy tính đánh số từ 1 đến 𝑛 được kết nối thành một mạng bởi 𝑚 đoạn cáp
mạng đánh số từ 1 đến 𝑚. Đoạn cáp mạng thứ 𝑖 có thông lượng 𝑤𝑖 kết nối hai máy 𝑢𝑖, 𝑣𝑖 cho phép
truyền dữ liệu theo cả hai chiều giữa hai máy này.

Một dãy các máy 𝑥1, 𝑥2,. . ,𝑥𝑝 trong đó giữa hai máy 𝑥𝑗 và 𝑥𝑗+1(𝑗 = 1,2, ..,𝑝 − 1) có đoạn cáp
nối được gọi là một đường truyền tin từ máy 𝑥1 tới máy 𝑥𝑝 . Thông lượng của đường truyền tin
được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên
đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kì và
giữa hai máy có không quá một đoạn cáp mạng nối chúng.

Người ta muốn nâng cấp mạng bằng cách tăng thông lư ợng của một số đoạn cáp nối trong mạng.
Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng ∆ (∆ > 0) ta phải trả một chi phí
đúng bằng ∆. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp
mạng 𝑖 đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy 𝑢𝑖 tới máy 𝑣𝑖.
Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất
Dữ liệu: Vào từ file văn bản UPGRANET.INP:
 Dòng thứ nhất: Chứa hai số nguyên dương 𝑛, 𝑚 (𝑛, 𝑚 ≤ 105)
 Dòng thứ 𝑖 trong số 𝑚 dòng tiếp theo chứa ba số nguyên dương 𝑢𝑖,𝑣𝑖, 𝑤𝑖 (𝑤𝑖 ≤ 106),
𝑖 = 1,2, …, 𝑚.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách
Kết quả: ghi ra file văn bản UPGRANET.OUT một số nguyên duy nhất là tổng chi phí nâng cấp
theo phương án tìm được.

Ví dụ

UPGRANET.INP                 UPGRANET.OUT
 6 7                          5
 1 2 6
 1 3 5
 2 4 3
 3 4 9
 4 5 4
 4 6 8
 5 6 7


Ràng buộc: 50% số test ứng với 50% số điểm của bài có 𝑛                 ≤   100.