Đị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 đến đỉnh nghĩa là có thể kết nối từ đến nhưng không theo chiều ngược lại. Nếu cài phần mềm trên các đỉnh , , và (tô màu) thì đỉnh và đỉnh 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 và : số đỉnh và số cạnh của mạng. Các đỉnh được đánh số , trong đó đỉnh và đỉnh là hai đỉnh muốn liên lạc với nhau. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và (), cho biết có một cạnh có hướng từ đến .
Sau mô tả cuối cùng là một dòng chứa hai số .
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 đến đỉnh chỉ dùng các đỉnh có phần mềm, và cũng có một đường đi từ đỉnh đến đỉnh 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 và đỉnh .
Nếu đỉnh và đỉnh 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
- , .
- ; 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á mạng, tổng của các mạng trong một file không quá .
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 và dùng chung các đỉnh . Mạng 2: không có đường đi từ đỉnh đến đỉnh . |
| 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 và , đoạn được cả hai đường đi theo cùng một chiều, cần đỉnh; đường đi ngắn nhất dẫn đến đỉnh. Mạng 2: có cạnh lặp và cạnh từ một đỉnh đến chính nó. Mạng 3: đỉnh không đi được đến đỉnh . |
Bình luận