Bài truyền tin trên mạng
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (44.69 KB, 1 trang )
Truyền tin trên mạng
Trong một mạng gồm n máy tính đánh số từ 1 đến N. Sơ đồ nối mạng đựơc cho bởi hệ thống
gồm M kênh nối trực tiếp giữa một số cặp máy tính trong mạng. Biết chi phí truyền một đơn vị
thông tin theo mỗi kênh nối của mạng.
Người ta cần chuyển một bức thông điệp từ máy S đến T. Để đảm bảo an toàn, người ta muốn
chuyển bức thông điệp này theo K đường truyền tin khác nhau. Hai đường truyền tin được gọi là
khác nhau nếu không có bất cứ kênh nối trực tiêp nào được dùng chung trên cả hai đường
truyền tin. Chi phí của một đường truyền tin được hiểu là chi phí trên các kênh của nó.
Yêu cầu
: Giả sử bức thông điệp có độ dài là 1 đơn vị thông tin, hãy tìm cách chuyển thông tin
từ S đến T sao cho tổng chi phí chuyển thông tin (bằng tổng chi phí theo cả K đường truyền tin)
là nhỏ nhất.
Dữ liệu:
Vào từ file văn bản Ttin.INP:
- Dòng đầu tiên ghi năm số N,M,S,T,K cách nhau bởi dấu cách (N≤100).
- M dòng sau mỗi dòng ghi ba số d
i
, c
i
, g
i
: trong đó d
i
, c
i
là chỉ số của hai máy tương ứng có kênh
nỗi và g
i
(nguyên dương) là chi phí để truyền một đơn vị thông tin từ máy d
i
đến máy c
i
và ngựơc
lại (i=1 n).
Kết quả:
Ghi ra file văn bản TTIN.OUT:
- Dòng đầu tiên ghi chi phí truyền thông điệp theo cách tìm đựơc
- K dòng tiếp theo, mỗi dòng ghi đường truyền tin dưới dạng dãy có thứ tự các máy bắt đầu từ
máy S và kết thúc ở máy T.
- Nếu không tìm đủ K đường đưa ra một dòng duy nhất: NO SOLUTION.
Ví dụ:
