trang chủ / đề bài / icpcwf06_j

Định tuyến

Đề bài

Mô tả

Khi ngày càng nhiều giao dịch giữa các công ty và cá nhân được thực hiện qua Internet, việc liên lạc an toàn trở thành một mối quan tâm lớn. Công ty Giao thức Mật mã Internet (ICPC) chuyên về các giao dịch an toàn giữa doanh nghiệp với doanh nghiệp được thực hiện qua mạng. Hệ thống do ICPC phát triển có một điểm đặc biệt trong cách triển khai trên mạng.

Một mạng như Internet có thể được mô hình hoá bằng một đồ thị có hướng: các đỉnh là máy tính hoặc bộ định tuyến, các cạnh là kết nối trực tiếp, dữ liệu có thể truyền theo chiều của cạnh. Để hai đỉnh liên lạc được với nhau, dữ liệu phải được truyền theo một đường đi có hướng từ đỉnh thứ nhất đến đỉnh thứ hai, và theo một đường đi có hướng từ đỉnh thứ hai đến đỉnh thứ nhất.

graph directed
8 12
1 3
3 4
4 2
2 5
5 6
6 1
1 7
7 1
8 7
7 8
8 2
2 8
highlight 1 2 7 8

Mũi tên từ đỉnh X đến đỉnh Y nghĩa là có thể kết nối từ X đến Y nhưng không theo chiều ngược lại. Nếu cài phần mềm trên các đỉnh 1, 2, 7 và 8 (tô màu) thì đỉnh 1 và đỉnh 2 liên lạc được với nhau. Còn những cách cài khác, nhưng đây là cách tốn ít nhất. Hình này ứng với mạng thứ nhất của ví dụ 1.

Để thực hiện một giao dịch an toàn, hệ thống của ICPC yêu cầu cài phần mềm của họ không chỉ trên hai đỉnh đầu cuối muốn liên lạc, mà trên cả mọi đỉnh trung gian của hai đường đi nối hai đỉnh đầu cuối. Vì ICPC tính tiền khách hàng theo số bản phần mềm phải cài, sẽ rất hữu ích nếu có một chương trình tìm cách nối rẻ nhất cho một mạng và một cặp đỉnh đầu cuối bất kỳ.

Dữ liệu vào

Dữ liệu vào gồm nhiều mô tả mạng. Dòng đầu tiên của mỗi mô tả chứa hai số nguyên N và M: số đỉnh và số cạnh của mạng. Các đỉnh được đánh số 1,2,…,N, trong đó đỉnh 1 và đỉnh 2 là hai đỉnh muốn liên lạc với nhau. Tiếp theo là M dòng, mỗi dòng chứa hai số nguyên X và Y (1≤X,Y≤N), cho biết có một cạnh có hướng từ X đến Y.

Sau mô tả cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi mô tả mạng, in số thứ tự của nó trong dãy mô tả. Sau đó in số đỉnh ít nhất phải cài phần mềm sao cho có một đường đi có hướng từ đỉnh 1 đến đỉnh 2 chỉ dùng các đỉnh có phần mềm, và cũng có một đường đi từ đỉnh 2 đến đỉnh 1 với cùng tính chất đó. (Một đỉnh có thể nằm trên cả hai đường đi, nhưng một đường đi không nhất thiết phải chứa mọi đỉnh có phần mềm.) Số đỉnh này tính cả đỉnh 1 và đỉnh 2.

Nếu đỉnh 1 và đỉnh 2 không thể liên lạc với nhau, in IMPOSSIBLE thay cho kết quả.

Làm theo đúng định dạng trong ví dụ, và in một dòng trống sau kết quả của mỗi mạng.

Ràng buộc

  • 2≤N≤100, 0≤M≤104.
  • 1≤X,Y≤N; có thể có cạnh từ một đỉnh đến chính nó và cạnh lặp lại.
  • Mỗi file có không quá 100 mạng, tổng M của các mạng trong một file không quá 105.

Ví dụ

Input Output Giải thích
8 12
1 3
3 4
4 2
2 5
5 6
6 1
1 7
7 1
8 7
7 8
8 2
2 8
2 1
1 2
0 0
Network 1
Minimum number of nodes = 4

Network 2
IMPOSSIBLE

Mạng 1 là mạng trong hình: hai đường đi 1→7→8→2 và 2→8→7→1 dùng chung các đỉnh 7,8. Mạng 2: không có đường đi từ đỉnh 2 đến đỉnh 1.
6 9
1 3
3 4
4 5
5 2
2 3
5 1
1 6
6 2
4 4
2 4
2 2
1 2
2 1
2 1
3 2
1 3
3 2
0 0
Network 1
Minimum number of nodes = 5

Network 2
Minimum number of nodes = 2

Network 3
IMPOSSIBLE

Mạng 1: chọn 1→3→4→5→2 và 2→3→4→5→1, đoạn 3→4→5 được cả hai đường đi theo cùng một chiều, cần 5 đỉnh; đường đi ngắn nhất 1→6→2 dẫn đến 6 đỉnh. Mạng 2: có cạnh lặp và cạnh từ một đỉnh đến chính nó. Mạng 3: đỉnh 2 không đi được đến đỉnh 1.

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