trang chủ / đề bài / icpc26_mt_k

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 N trạm trung chuyển và M 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 0, 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 0. Một trạm không có tuyến bay nào vừa có bán bậc vào bằng 0 vừa có bán bậc ra bằng 0, 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 e, phải có ít nhất Le và nhiều nhất Re drone bay qua tuyến đó.
  • Với mỗi trạm trung chuyển v, tổng số drone ghé qua trạm phải nằm trong đoạn [Av,Bv]. Mỗi drone có hành trình đi qua trạm v (xuất phát tại v, bay ngang qua v hoặc kết thúc tại v) đượ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 N và M (1≤N≤1000, 1≤M≤5000). Các trạm được đánh số từ 1 đến N.
  • N dòng tiếp theo, dòng thứ v chứa hai số nguyên Av,Bv (0≤Av≤Bv≤105) mô tả ràng buộc của trạm v.
  • M dòng tiếp theo, mỗi dòng chứa bốn số nguyên u,v,L,R (1≤u,v≤N; 0≤L≤R≤105) mô tả một tuyến bay một chiều từ u đến v với ràng buộc số drone bay qua tuyến phải nằm trong đoạn [L,R]. Đồ 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 −1.

Ràng buộc

  • 1≤N≤1000, 1≤M≤5000.
  • 0≤Av≤Bv≤105.
  • 1≤u,v≤N, 0≤L≤R≤105.
  • Đồ 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 1→2 và 2→4 cần ít nhất 1 drone, còn trạm 3 cần 1 đến 2 drone ghé qua, nên phải có drone đi 1→3→4. Dùng 2 drone: một drone đi 1→2→4, drone còn lại đi 1→3→4. Khi đó mỗi tuyến có 1 drone, trạm 2 và trạm 3 mỗi trạm có 1 drone ghé qua, trạm 1 và trạm 4 mỗi trạm có 2 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 1, nên không thể dùng ít hơn 2 drone.
3 1
0 5
0 5
1 4
1 2 2 3
3 Ví dụ bổ sung. Tuyến 1→2 cần ít nhất 2 drone. Trạm 3 không có tuyến bay nào và cần ít nhất 1 drone ghé qua: drone đó xuất phát và kết thúc ngay tại trạm 3. Tổng cộng 3 drone.
2 1
0 1
0 1
1 2 2 3
-1 Ví dụ bổ sung. Tuyến 1→2 cần ít nhất 2 drone, nhưng trạm 1 chỉ cho phép nhiều nhất 1 drone ghé qua.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0