Drone
Đề bài
Mô tả
Tại thành phố Đà Nẵng của tương lai, mạng lưới giao thông trên không được mô hình hóa bằng một đồ thị có hướng không chu trình (DAG) gồm trạm trung chuyển và tuyến bay một chiều. Để đảm bảo an ninh, trung tâm điều hành cần triển khai các đội drone tuần tra. Mỗi drone xuất phát từ một trạm bất kỳ có bán bậc vào bằng , bay qua các tuyến bay hợp lệ và kết thúc hành trình tại một trạm bất kỳ có bán bậc ra bằng . Một trạm không có tuyến bay nào vừa có bán bậc vào bằng vừa có bán bậc ra bằng , nên một drone có thể xuất phát và kết thúc ngay tại trạm đó mà không bay tuyến nào.
Hệ thống áp dụng các quy định an toàn nghiêm ngặt:
- Với mỗi tuyến bay , phải có ít nhất và nhiều nhất drone bay qua tuyến đó.
- Với mỗi trạm trung chuyển , tổng số drone ghé qua trạm phải nằm trong đoạn . Mỗi drone có hành trình đi qua trạm (xuất phát tại , bay ngang qua hoặc kết thúc tại ) được tính đúng một lần.
- Việc chế tạo và vận hành drone vô cùng tốn kém.
Yêu cầu: Hãy tính số drone ít nhất cần dùng để tạo thành một hệ thống tuyến bay thỏa mãn tất cả các quy định trên.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên dương và (, ). Các trạm được đánh số từ đến .
- dòng tiếp theo, dòng thứ chứa hai số nguyên () mô tả ràng buộc của trạm .
- dòng tiếp theo, mỗi dòng chứa bốn số nguyên (; ) mô tả một tuyến bay một chiều từ đến với ràng buộc số drone bay qua tuyến phải nằm trong đoạn . Đồ thị được đảm bảo không có chu trình.
Dữ liệu ra
- In ra một dòng chứa một số nguyên là số drone ít nhất cần dùng.
- Nếu không tồn tại cách bố trí hợp lệ, in ra .
Ràng buộc
- , .
- .
- , .
- Đồ thị các tuyến bay không có chu trình.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 1 5 1 2 1 2 0 5 1 2 1 2 1 3 0 5 2 4 1 2 3 4 0 5 |
2 | Tuyến và cần ít nhất drone, còn trạm cần đến drone ghé qua, nên phải có drone đi . Dùng drone: một drone đi , drone còn lại đi . Khi đó mỗi tuyến có drone, trạm và trạm mỗi trạm có drone ghé qua, trạm và trạm mỗi trạm có drone. Hai yêu cầu trên cần hai hành trình khác nhau xuất phát từ trạm , nên không thể dùng ít hơn drone. |
| 3 1 0 5 0 5 1 4 1 2 2 3 |
3 | Ví dụ bổ sung. Tuyến cần ít nhất drone. Trạm không có tuyến bay nào và cần ít nhất drone ghé qua: drone đó xuất phát và kết thúc ngay tại trạm . Tổng cộng drone. |
| 2 1 0 1 0 1 1 2 2 3 |
-1 | Ví dụ bổ sung. Tuyến cần ít nhất drone, nhưng trạm chỉ cho phép nhiều nhất drone ghé qua. |
Bình luận