Tàu cao tốc
Đề bài
Mô tả
Năm 2207, đất nước PVH trở thành một trong những quốc gia nhộn nhịp nhất thế giới. Để đáp ứng nhu cầu đi lại giữa các thành phố đang tăng nhanh, đồng thời giảm khí thải từ máy bay, chính phủ dự định xây dựng một hệ thống tàu cao tốc.
Đất nước PVH có thành phố, đánh số từ đến . Mỗi thành phố có đúng một nhà ga trung tâm, nơi các chuyến tàu khởi hành và đến. Hệ thống đường ray hiện tại cho phép tàu chạy thẳng giữa mọi cặp thành phố. Khoảng cách giữa nhà ga của hai thành phố và là , với cho mọi cặp và cho mọi .
Chính phủ dự định vận hành một số tuyến tàu. Mỗi tuyến khởi hành từ một nhà ga, đi qua một số nhà ga khác và kết thúc ở một nhà ga nào đó. Trên một tuyến, tàu không được đi qua một nhà ga quá một lần và tuyến có không quá nhà ga (tính cả ga đầu và ga cuối). Chi phí vận hành một tuyến là tổng khoảng cách giữa các cặp nhà ga liên tiếp.
Chính xác hơn, một tuyến là một dãy số nguyên thoả mãn:
- ;
- ;
- đôi một phân biệt.
Chi phí vận hành tuyến này là .
Có cặp thành phố quan trọng, giữa chúng có hàng triệu người đi lại mỗi năm. Với mỗi cặp quan trọng , chính phủ muốn có ít nhất một tuyến đi qua cả và . Thứ tự không quan trọng: hai cặp và được coi là một.
Hãy giúp đất nước PVH thiết kế các tuyến tàu sao cho mọi cặp quan trọng đều được phục vụ và tổng chi phí vận hành các tuyến là nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên: số bộ test. Mỗi bộ test có dạng:
- Dòng đầu tiên chứa ba số nguyên , , (, ).
- Trong dòng tiếp theo, dòng thứ () chứa số nguyên ().
- dòng cuối, mỗi dòng chứa hai số nguyên và () mô tả một cặp thành phố quan trọng.
Dữ liệu đảm bảo:
- tổng trên tất cả các bộ test không vượt quá ;
- tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test:
- Dòng đầu tiên chứa hai số nguyên và : chi phí vận hành nhỏ nhất và số tuyến tàu.
- dòng tiếp theo, mỗi dòng chứa một số nguyên () và tiếp theo là số nguyên () mô tả một tuyến tàu.
Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ.
Ràng buộc
- ,
- Các cặp quan trọng có .
- Tổng trên tất cả các bộ test không vượt quá , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 3 6 1 2 3 4 5 6 7 8 9 10 1 2 2 3 1 3 3 4 4 5 3 5 5 4 6 1 2 3 4 5 6 7 8 9 10 1 2 2 3 1 3 3 4 4 5 3 5 |
20 2 3 4 3 5 3 2 1 3 17 2 4 4 1 3 5 3 2 1 3 |
Bộ test thứ nhất: tuyến (chi phí ) phục vụ các cặp , , ; tuyến (chi phí ) phục vụ , , . Bộ test thứ hai cho phép nhà ga mỗi tuyến, tuyến có chi phí . |
| 1 4 2 2 1 100 100 100 100 1 1 3 2 4 |
200 2 2 1 3 2 2 4 |
Mỗi tuyến chỉ có tối đa nhà ga nên mỗi cặp quan trọng cần một tuyến riêng và , tổng chi phí . |
Bình luận