Duyên hải Bắc Bộ 2024 - 10 - Mạng công ty
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Công ty của Alice có ~n~ máy tính, các máy tính được đánh số từ ~1~ đến ~n~. Hiện tại đang có ~m~ (~m \ge n-1~) dây nối giữa các máy tính, dây nối thứ ~k~ (~1 \le k \le m~) nối hai máy tính ~u_k, v_k~ (~u_k \ne v_k~) và giúp truyền tin theo cả hai chiều giữa hai máy, có thể có nhiều dây nối giữa hai máy tính. Hiện tại, ~n~ máy tính có thể không liên thông với nhau, Alice có thể tháo dây nối để đấu nối lại với mong muốn làm cho ~n~ máy tính liên thông, cụ thể, cô có thể thực hiện:
Tháo một đầu nối của dây thứ ~k~ để đấu nối sang máy tính khác, hành động này mất chi phí ~c_k~;
Tháo cả hai đầu nối của dây thứ ~k~ để đấu nối sang hai máy tính khác, hành động này mất chi phí ~2 \times c_k~.
Yêu cầu: Hãy giúp Alice tính chi phí ít nhất cần thực hiện để liên thông được ~n~ máy tính.
Input
Dòng đầu chứa hai số nguyên dương ~n, m~ (~n \le 10^5~; ~n-1 \le m \le 2 \times 10^5~);
Dòng thứ ~k~ (~1 \le k \le m~) trong ~m~ dòng tiếp theo chứa ba số nguyên dương ~u_k, v_k, c_k~ (~c_k \le 10^6~).
Output
Một dòng chứa một số là chi phí ít nhất tìm được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~50\%~ | ~c_i = 1~ |
| 2 | ~25\%~ | ~m, n \le 1000~ |
| 3 | ~25\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
3 3
1 2 1
1 2 2
1 3 1
Sample Output 1
0
Sample Input 2
3 3
1 2 1
1 2 2
1 2 3
Sample Output 2
1
Bình luận