Hướng dẫn giải của BÀI 6: THIẾT KẾ MẠNG MÁY TÍNH (NETWORK)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
- Xác định các thành phần liên thông giữa các trạm bằng DFS/BFS.
- Với mỗi thành phần liên thông:
- Gom toàn bộ các máy tính thuộc các trạm trong thành phần đó.
- Sắp xếp các máy tính giảm dần theo số cổng kết nối ~c_i~.
- Dựng cây bằng thuật toán tương tự BFS:
- Chọn máy có ~c_i~ lớn nhất làm gốc.
- Duyệt các máy đã vào cây theo thứ tự mức, nối các máy chưa vào cây (ưu tiên ~c_i~ lớn) vào máy này cho tới khi hết cổng kết nối.
- Tính độ trễ ~L~:
- Với mỗi cây vừa dựng, tìm đường kính của cây bằng 2 lượt DFS/BFS.
- ~L = \max(\text{đường kính các cây})~.
- Chi phí: ~f = E \times n + L~.
- Độ phức tạp: ~\mathcal{O}((n + m) \log n)~.
Bình luận