Thu phí không dừng
Đề bài
Mô tả
Ở một vùng đất xa thật xa, nơi cải cách hành chính bỏ cấp quận chưa được thực hiện, có thành phố Nogias sôi động, được chia thành bốn quận, mỗi quận mang một vẻ đẹp riêng. Quận 1 là "trái tim" của Nogias, nơi đặt các tòa nhà hành chính. Quận 2 là nơi có vô số khu dân cư sang trọng, giàu có. Quận 3 tập trung phần lớn các tòa nhà văn phòng của thành phố. Còn quận 4 được cả người dân Nogias lẫn du khách nước ngoài mệnh danh là thiên đường ẩm thực. Các quận lại được chia thành phường, đánh số từ đến , sao cho mỗi quận có ít nhất một phường.
Mạng lưới giao thông của thành phố gồm con đường hai chiều, mỗi con đường nối hai phường. Có thể có nhiều con đường cùng nối một cặp phường, thậm chí có cả những con đường nối một phường với chính nó: dù sao thì càng nhiều đường càng tốt, mặc kệ chi phí bảo trì. Dữ liệu đảm bảo với mọi cặp phường , luôn tồn tại ít nhất một đường đi giữa chúng.
Nếu phải chê Nogias một điều, thì đó là vô số vụ kẹt xe. Mỗi ngày, hàng trăm nghìn xe máy tràn ngập các con đường, tạo nên một trải nghiệm thật sự ác mộng. Là một trong những đội xuất sắc nhất của Cuộc thi Quy hoạch Đô thị Quốc tế (ICPC), bạn được hội đồng thành phố thuê để giải quyết vấn đề này. Sau khi phân tích, bạn nhận thấy phần lớn lưu lượng giao thông đến từ những người sống ở một quận nhưng làm việc ở quận khác. Cụ thể, các cặp quận sau đây gây áp lực giao thông rất lớn:
- quận 1 và quận 2;
- quận 2 và quận 3;
- quận 3 và quận 4;
- quận 4 và quận 1.
Vì không thể di dời người dân, còn đề xuất xây dựng hạ tầng giao thông công cộng của bạn thì bị gạt đi ngay lập tức, bạn chọn phương án duy nhất còn lại: thu phí điện tử không dừng (ETC)! Kế hoạch là lắp đặt ETC trên một số con đường sao cho với mọi cặp quận có vấn đề , mọi đường đi bắt đầu tại một phường thuộc quận và kết thúc tại một phường thuộc quận (hoặc ngược lại) đều phải đi qua ít nhất một con đường có lắp ETC.
Chẳng ai bất ngờ khi kế hoạch thiên tài của bạn được thành phố duyệt ngay, kèm theo một lưu ý nhỏ: người dân thực sự không thích trả tiền. Vì vậy, kế hoạch của bạn còn phải có số con đường được lắp ETC là nhỏ nhất.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa hai số nguyên và (; ): số phường và số con đường.
- Dòng thứ hai chứa số nguyên (), trong đó là quận chứa phường .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (), biểu diễn một con đường nối hai phường và .
Dữ liệu đảm bảo:
- Mỗi quận trong bốn quận có ít nhất một phường, và với mọi cặp phường , luôn tồn tại ít nhất một đường đi giữa chúng.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra số con đường ít nhất cần lắp ETC.
Ràng buộc
- .
- , .
- , mỗi quận có ít nhất một phường.
- ; đồ thị liên thông, có thể có nhiều đường nối cùng một cặp phường và đường nối một phường với chính nó.
- Tổng và tổng qua tất cả các bộ dữ liệu đều không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 16 16 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 1 4 2 4 3 4 4 8 5 8 6 8 7 8 8 12 9 12 10 12 11 12 12 16 13 16 14 16 15 16 16 4 |
4 | Phường , , , lần lượt là trung tâm của quận , , , ; các phường còn lại của mỗi quận nối với trung tâm quận mình. Một phương án tối ưu là lắp ETC trên bốn con đường , , và . |
| 2 4 3 1 2 3 4 1 2 2 3 3 4 5 7 1 3 2 4 1 1 2 2 3 3 4 4 5 1 2 5 5 4 1 |
3 3 |
Ví dụ bổ sung (không có trong đề gốc). Ở bộ dữ liệu thứ nhất, cả ba con đường đều nối một cặp quận có vấn đề. Ở bộ dữ liệu thứ hai, cần lắp ETC trên các con đường , và ; hai con đường (quận và quận ), con đường (quận và quận ) và con đường không cần lắp. |
Bình luận