Bài tập cây khung nhỏ nhất
Bài tập 1 : Mạng an toàn Cho một mạng N (N <= 20) máy tính được đánh số từ 1 đến N. Sơ đồ mạng được cho bởi hệ gồm M kênh (đoạn) nối trực tiếp giữa một số cặp máy trong mạng, m kênh tương ứng với m cặp. Cho biết chi phí ...
Bài tập 1 : Mạng an toàn
Cho một mạng N (N <= 20) máy tính được đánh số từ 1 đến N. Sơ đồ mạng được cho bởi hệ gồm M kênh (đoạn) nối trực tiếp giữa một số cặp máy trong mạng, m kênh tương ứng với m cặp. Cho biết chi phí truyền 1 đơn vị thông tin theo mỗi kênh của mạng.
Người ta cần chuyển một bức thông điệp từ máy s đến máy t. Để đảm bảo an toàn, người ta chuyển bức thông điện này theo hai đường truyền tin khác nhau (tức không có kênh nào) của mạng được sử dụng trong cả hai đường truyền tin; cho phép hai đường truyền tin cùng đi qua một số máy tính). Chi phí của một đường truyền được hiểu là tổng chi phí trên các kênh của nó. Đơn giá đường truyền từ máy s sang máy t được tính như sau:
Với hai máy s và t, cùng bức thông điệp có độ dài là 1 đơn vị thông tin, đơn giá truyền cho cặp (s, t) được tính bằng tổng chi phí chuyển thông điệp an toàn (bằng tổng chi phí của hai đường truyền tin) là nhỏ nhất.
Mạng truyền tin nói trên thỏa mãn tính chất an toàn theo nghĩa là từ một máy bất kỳ luôn truyền được (một cách an toàn) thông điệp tới một máy bất kỳ khác. Khi một mạng an toàn, người ta tính được đơn giá của mạng là tổng đơn giá mọi đường truyền từ một máy bất kỳ tới một máy bất kỳ khác.
Ma trận đơn giá của mạng là mảng hai chiều A có N dòng và N cột, mà giá trị phần tử A[i, j] chính là đơn giá từ máy i sang máy j.
Câu 1: Cho trước một mạng, hãy kiểm ra tính an toàn của mạng đó.
Câu 2: Khi mạng không an toàn được phép bổ sung một số kênh truyền để nó trở thành an toàn. Đơn giá mỗi kênh truyền bổ sung theo được coi bằng hai lần giá trị cực đại đơn giá các kênh đã có. Mọi kênh bổ sung được coi có đơn giá như nhau. Hãy tìm cách bổ sung các kênh mới mà đơn giá mạng là nhỏ nhất.
Câu 3: Khi mạng an toàn hoặc sau khi bổ sung kênh để mạng an toàn, hãy in ra đơn giá mạng và ma trận đơn giá.
Dữ liệu vào:
cho trong file INP.B2 với cấu trúc như sau:
Dòng đầu tiên ghi 2 số n, m cách nhau bởi dấu cách.
Mỗi dòng thứ i trong số m dòng tiếp theo ghi thông tin về kênh nối thứ i của mạng gồm 3 số d[i], c[i], g[i] trong đó d[i], c[i] là chỉ số của hai máy tương ứng với kênh này 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] theo kênh này. Các giá trị g[i] cho trước không vượt quá 40 (và như vậy đơn giá các kênh bổ sung không vượt quá 80).
Kết quả:
ghi ra file OUT.B2 theo qui cách sau:
Dòng đầu tiên ghi 1 số nguyên p thể hiện mạng có an toàn hay không và p có ý nghĩa là số lượng kênh cần bổ sung. p=0 có nghĩa mạng an toàn; p>0 có nghĩa mạng không an toàn và cần bổ sung p kênh nữa để mạng an toàn với chi phí bổ sung ít nhất.
p dòng tiếp theo ghi p kênh bổ sung. Cách ghi như trong file dữ liệu vào.
Dòng tiếp theo ghi đơn giá của mạng an toàn.
N dòng tiếp theo ghi ma trận đơn giá của mạng an toàn: mỗi hàng của ma trận ghi trên một dòng.
Bài tập 2: Xây dựng đường ống nước
Có 1 trạm cấp nước và N điểm dân cư. Hãy xây dựng chương trình thiết kế tuyến đường ống nước cung cấp đến mọi nhà sao cho tổng chiều dài đường ống phải dùng là ít nhất. Giả sử rằng các đường ống chỉ được nối giữa 2 điểm dân cư hoặc giữa trạm cấp nước với điểm dân cư.
