ĐỀ BÀI
Để tránh hiện tượng một gói tin bị
truyền đi liên tục trong mạng nên mỗi gói tin khi gởi đi sẽ có một thông số thời
gian tồn tại (TTL), thông số này cho biết số lượng nút (trạm truyền tin, máy
tính,…) có thể truyền lại gói tin này trước khi gói tin bị hủy. Cứ mỗi lần có một
nút nhận được gói tin và truyền lại thì TTL của gói tin sẽ bị giảm đi 1. Trong
trường hợp gói tin này đến được đích, giá tị TTL sẽ được bỏ qua. Tuy nhiên, nếu
gói tin cần phải được truyền đi tiếp mà giá trị TTL bằng 0 thì gói tin sẽ không
thể truyền đi tiếp tục.
Yêu cầu: cho biết thông tin về số
lượng nút trong mạng cũng như thông tin các đường truyền của mạng, hãy xác định
số nút không thể nhận được gói tin khi có một gói tin được gởi đi từ một nút với
một giá trị TTL nào đó.
Ví dụ: với thông tin mạng như
hình vẽ bên thì:
Nếu có một gói tin với TTL là 2
được gởi đi từ nút 35 thì nó có thể được truyền đến các nút 15, 10, 55, 50, 40,
20 và 60. Gói tin này không thể truyền đến các nút 30, 47, 25, 45 và 65, do giá
trị TTL sẽ có giá trị bằng 0 khi được truyền đến các nút 10, 20, 50 và 60. Nếu
chúng ta tăng giá trị TTL này lên 3 thì bắt đầu từ 35 gói tin sẽ được truyền đến
tất cả các nút khác ngoại trừ nút 45.
Dữ liệu vào:
Có nhiều bộ dữ liệu, mỗi bộ dữ liệu
cho biết thông tin cho một mạng và các truy vấn cho mạng này được mô tả như
sau:
-
Dòng đầu ghi số nguyên dương n cho biết số lượng đường truyền có
trong mạng (các bộ dữ liệu sẽ kết thúc khi n
= 0).
-
Tiếp theo là n
cặp số, mỗi cặp số u và v cho biết có đường truyền trực tiếp giữa
2 nút u và v (giữa 2 nút chỉ có tối đa 1 đường truyền trực tiếp và số lượng nút
cho mỗi mạng tối đa là 30).
-
Tiếp theo là các truy vấn, mối truy vấn gồm 1 cặp
số u và t cho biết có gói tin được phát từ nút u và có giá trị TTL là t,
các truy vấn sẽ kết thúc bằng một cặp số 0 0.
Kết quả:
Ứng với mỗi truy vấn hãy cho biết
số lượng nút trong mạng tương ứng mà gói tin với giá trị TTL được cho không thể
truyền đến, các câu trả lời được đánh thứ tự bắt đầu từ 1 và được mô tả như ví
dụ.
Ví dụ:
Input
16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 11
4 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0
Output
Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
HƯỚNG DẪN
Với mỗi truy vấn ta sử dụng BFS để duyệt trên đồ thị bắt đầu từ u với số bước duyệt không quá t sau đó đếm xem có bao nhiêu nút chưa được duyệt (hoặc trong quá trình duyệt ta đếm số nút được đã được duyệt đề từ đó tìm được kết kết quả).
No comments:
Post a Comment