Đạp ga trên thảo nguyên
Đề bài
Mô tả
Chân ga đạp sát sàn. Bánh xe rít lên. Còi hú vang. Các xe cấp cứu làm mọi điều cần thiết để đến nơi nhanh nhất có thể. Thời gian là yếu tố sống còn vì tính mạng con người thường phụ thuộc vào nó.
Cung cấp dịch vụ cấp cứu luôn là một thách thức, đặc biệt ở những vùng thưa dân như thảo nguyên Kazakhstan. Chi phí xây dựng cơ sở hạ tầng rất cao so với số người được phục vụ. Vì vậy cần giảm tối đa cả số con đường lẫn số xe. Mặt khác, giảm thời gian phản ứng của dịch vụ cấp cứu cũng là điều thiết yếu.
Bài toán này xét một mạng lưới đường đã tối thiểu hóa số con đường, nghĩa là giữa hai ngôi làng bất kỳ có đúng một đường đi. Nhờ một khoản tài trợ của chính phủ, Sở Cứu hỏa thảo nguyên Kazakhstan vừa mua được một số xe cứu hỏa mới tinh. Sở muốn đặt trạm cứu hỏa ở một số làng và phân bổ các xe cứu hỏa vào đó sao cho thời gian phản ứng được bảo đảm là tốt nhất.
Nhiệm vụ của bạn là tìm cách đặt các xe cứu hỏa tối ưu, sao cho thời gian cần thiết để một xe cứu hỏa đến được bất kỳ ngôi làng nào là nhỏ nhất. Bạn có thể bỏ qua thời gian tập hợp đội cứu hỏa, thời gian khởi động xe cũng như thời gian đi qua các ngôi làng. Thời gian phản ứng chỉ được tính bằng thời gian di chuyển trên các con đường.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên: số ngôi làng () và số xe cứu hỏa ().
Tiếp theo là dòng, được đánh số từ đến . Dòng số chứa hai số nguyên () và (), cho biết có một con đường hai chiều nối làng với làng , đi hết thời gian .
Dữ liệu ra
In ra thời gian phản ứng nhỏ nhất có thể bảo đảm được khi đặt các xe cứu hỏa vào ngôi làng.
Ràng buộc
- , .
- , với mọi .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 1 8 2 7 2 7 3 6 3 5 |
8 | Đặt hai xe ở làng và làng . Làng và làng cách làng lần lượt và ; làng và làng cách làng lần lượt và . Không thể bảo đảm thời gian nhỏ hơn . |
| 3 3 1 1000 2 1000 |
0 | Có đủ xe để đặt một xe ở mỗi làng. |
Bình luận