Vành đai Aegis
Đề bài
Mô tả
Trong vành đai phòng thủ không gian Aegis, một hệ thống gồm trạm tiền tiêu được bố trí thành một vòng khép kín, đánh số từ đến theo chiều kim đồng hồ.
Giữa hai trạm kề nhau trên vòng có một dây cáp điện hai chiều:
- Dây cáp thứ nối trạm và trạm (với ); ngắt dây này tiết kiệm được lượng năng lượng .
- Dây cáp thứ nối trạm và trạm ; ngắt dây này tiết kiệm được lượng năng lượng .
Bộ chỉ huy quân sự thiết lập liên kết chiến lược khẩn cấp. Liên kết thứ yêu cầu hai trạm và () phải giữ được liên lạc với nhau theo mạng các dây cáp còn hoạt động.
Để hỗ trợ điều phối, bộ chỉ huy đề xuất phương án bảo trì độc lập. Trong phương án thứ , bộ chỉ huy chỉ định một khu vực chiến lược gồm các dây cáp có chỉ số liên tiếp từ đến ():
- Mọi dây cáp nằm ngoài khu vực phải tiếp tục hoạt động.
- Trong khu vực , bộ chỉ huy muốn ngắt một tập con các dây cáp sao cho tổng năng lượng tiết kiệm được là lớn nhất, đồng thời mọi liên kết trong liên kết chiến lược trên toàn vành đai vẫn không bị gián đoạn.
Hãy xác định tổng năng lượng tiết kiệm lớn nhất có thể đạt được trong khu vực của mỗi phương án bảo trì.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, , ): số trạm tiền tiêu, số liên kết chiến lược và số phương án bảo trì.
- Dòng thứ hai chứa số nguyên dương (): năng lượng tiết kiệm được khi ngắt từng dây cáp tương ứng.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và (, ): hai trạm của liên kết chiến lược thứ .
- dòng tiếp theo, dòng thứ chứa hai số nguyên và (): khu vực của phương án bảo trì thứ .
Dữ liệu ra
In ra dòng, mỗi dòng chứa một số nguyên là tổng năng lượng tiết kiệm lớn nhất của phương án tương ứng.
Ràng buộc
- , , .
- .
- , .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 2 10 20 15 30 40 1 3 2 4 1 5 2 4 |
70 30 |
Vành đai có dây cáp với và liên kết , . Phương án (): khu vực là cả vòng; có thể ngắt đồng thời hai dây và mà cả hai cặp và vẫn liên lạc được, tiết kiệm . Phương án (): khu vực gồm , các dây phải giữ nguyên; không thể ngắt đồng thời hai dây nào trong khu vực vì sẽ làm đứt ít nhất một liên kết, nên chỉ ngắt dây có lợi nhất là , tiết kiệm . |
| 6 1 3 5 1 4 2 3 6 2 5 1 6 2 4 3 3 |
14 7 4 |
Liên kết cho phép ngắt nhiều dây cùng lúc khi tất cả nằm trên cùng một cung giữa trạm và trạm : cung hoặc cung . Phương án : ngắt , tiết kiệm . Phương án : ngắt , tiết kiệm . Phương án : chỉ ngắt , tiết kiệm . |
Bình luận