trang chủ / đề bài / icpcwf07_j

Đường hầm

Đề bài

Mô tả

Khốn kiếp! Một điệp viên điển trai bằng cách nào đó đã thoát khỏi cái bẫy chết người công phu của bạn, hạ gục đám lính gác và đánh cắp kế hoạch thống trị thế giới tối mật của bạn. Giờ hắn đang chạy tự do trong căn cứ núi lửa của bạn, đe doạ toàn bộ chiến dịch xấu xa. Phải chặn hắn lại trước khi hắn trốn thoát!

May thay, bạn đang theo dõi từng bước của điệp viên từ phòng điều khiển bí mật, và bạn đã lên kế hoạch cho đúng tình huống này. Căn cứ của bạn gồm một mạng lưới phức tạp các phòng, nối với nhau bằng các đường hầm không cắt nhau. Mỗi phòng đều có camera giám sát (cho phép bạn biết điệp viên đang ở đâu tại mọi thời điểm), và mỗi đường hầm đều có một khối thuốc nổ nhỏ, đủ mạnh để làm sập đường hầm đó vĩnh viễn. Điệp viên quá nhanh nên không thể bị chôn vùi khi đường hầm sập, vì vậy bạn phải làm sập các đường hầm một cách có chiến lược để ngăn hắn đi từ phòng xuất phát ra bên ngoài căn cứ.

Sửa chữa căn cứ rất tốn kém, nên bạn muốn phá huỷ càng ít đường hầm càng tốt. Hãy tìm một chiến lược làm sập ít đường hầm nhất, bất kể điệp viên khôn ngoan đến đâu. Để an toàn, bạn phải giả sử điệp viên biết rõ toàn bộ hệ thống đường hầm. Lợi thế chính của bạn là có thể làm sập đường hầm vào bất cứ lúc nào bạn muốn, dựa trên những gì bạn quan sát được khi điệp viên di chuyển qua các đường hầm.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên R và T, lần lượt là số phòng và số đường hầm của căn cứ. Các phòng được đánh số từ 1 đến R. Tiếp theo là T dòng, mỗi dòng chứa hai số nguyên x,y là số hiệu hai phòng ở hai đầu một đường hầm; số 0 nghĩa là đầu đó của đường hầm thông ra bên ngoài. Có thể có nhiều đường hầm nối cùng một cặp phòng.

Điệp viên luôn xuất phát ở phòng 1. Dữ liệu vào kết thúc bằng một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ 1) và số đường hầm ít nhất phải làm sập trong trường hợp xấu nhất. Làm theo đúng định dạng trong ví dụ và in một dòng trống sau mỗi bộ test.

Ràng buộc

  • 1≤R≤50, 1≤T≤1000.
  • 0≤x,y≤R, không có đường hầm mà cả hai đầu đều là 0.
  • Mỗi file có không quá 50 bộ test và tổng T trong một file không quá 20000.

Ví dụ

Input Output Giải thích
4 6
1 2
1 3
2 4
3 4
4 0
4 0
4 6
1 2
1 3
1 4
2 0
3 0
4 0
0 0
Case 1: 2

Case 2: 2

Bộ 1: làm sập ngay hai đường hầm nối phòng 4 ra ngoài. Bộ 2: chờ điệp viên rời phòng 1; nếu hắn vào phòng 2 thì làm sập hai đường hầm 2-0 và 2-1, hắn bị nhốt trong phòng 2 (tương tự với phòng 3, 4). Làm sập ngay từ đầu thì cần 3 đường hầm.
4 7
1 0
1 2
1 3
1 4
2 0
3 0
4 0
0 0
Case 1: 3

Làm sập ngay đường hầm 1-0, sau đó làm như bộ 2 của ví dụ trên: tổng cộng 3, trong khi muốn chặn ngay từ đầu thì cần 4 đường hầm.

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