Bài 4. Trạm tiếp sóng (5 điểm)
Trong thành phố có 𝑁 trạm tiếp sóng. Trên bản thiết kế xây dựng, trạm thứ 𝑖 có tọa độ là (𝑥 𝑖 , 𝑦 𝑖 ).
Giữa hai trạm 𝑖 và 𝑗, chi phí để liên kết hai trạm này với nhau là 𝑚𝑖𝑛(|𝑥 𝑖 − 𝑥 𝑗 |, |𝑦 𝑖 − 𝑦 𝑗 |). Lãnh đạo
thành phố muốn liên kết toàn bộ các trạm tiếp sóng với nhau (hai trạm được gọi là có liên kết với nhau
khi chúng có liên kết trực tiếp với nhau hoặc liên kết qua một số trạm trung gian khác).
Yêu cầu: hãy giúp lãnh đạo thành phố tính tổng chi phí nhỏ nhất để liên kết toàn bộ 𝑁 trạm tiếp sóng.
Dữ liệu: vào từ tệp BTS.INP:
• Dòng đầu tiên ghi số nguyên 𝑁 (2 ≤ 𝑁 ≤ 10 5 ) là số trạm tiếp sóng;
Trang 2/3
• 𝑁 dòng tiếp theo, dòng thứ 𝑖 ghi hai số nguyên 𝑥 𝑖 và 𝑦 𝑖 (1 ≤ 𝑖 ≤ 𝑁; 1 ≤ 𝑥 𝑖 ≤ 10 9 ; 1 ≤ 𝑦 𝑖 ≤ 10 9 )
là tọa độ của trạm tiếp sóng thứ 𝑖.
Kết quả: ghi ra tệp BTS.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất để liên kết các trạm tiếp
sóng trên.
Ví dụ:
BTS.INP BTS.OUT Giải thích5
5 Liên kết giữa trạm 2 và 4 với chi phí 2. 4 9
Liên kết giữa trạm 3 và 4 với chi phí 1.
9 5
Liên kết giữa trạm 2 và 5 với chi phí 1.
0 2
Liên kết giữa trạm 1 và 5 với chi phí 1.
7 1
Tổng chi phí sẽ là: 2 + 1 + 1 + 1 = 5.
3 4
Chú ý: các số trên cùng một dòng cách nhau bởi dấu cách.
• Có 50% số test ứng với 𝑁 ≤ 10 3 ;
• 50% số test còn lại không có điều kiện gì thêm.
Bạn đang xem bài 4. - Đề thi học sinh giỏi môn Tin học lớp 12 cấp thành phố năm 2020-2021 - Sở GD&ĐT Hà Nội (Đề số 1)
