Hướng dẫn giải của BÀI 5: MẠNG HÌNH SAO TỐI ƯU (NETWORK2)
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.
- Do không giới hạn số cổng kết nối (~c_i = n~), ta tìm các thành phần liên thông giữa các trạm bằng DFS/BFS.
- Trong mỗi thành phần liên thông có ~V~ máy:
- Chọn 1 máy làm tâm (hub).
- Nối ~V - 1~ máy còn lại trực tiếp vào máy tâm.
- Số cạnh sử dụng là ~V - 1~.
- Độ trễ nội bộ thành phần là 2 (nếu ~V > 2~), là 1 (nếu ~V = 2~), là 0 (nếu ~V = 1~).
- Tổng số cạnh ~E = \sum (V_i - 1)~, ~L = \max(L_i)~.
- Chi phí ~f = E \times n + L~.
Bình luận