Bài này yêu cầu tính tổng trọng số tối thiểu để 4 đỉnh cho trước liên thông. Tôi làm:
1) dùng Floyd để có được ngắn nhất giữa (u,v).
2) Lọc ra các đỉnh, canh liên quan đến 4 đỉnh này tạo thành đồ thị mới G1
3) Tìm cây khung bé nhất trên G1
Tôi biết bị sai ở thuật toán vì có thể lấy các cạnh không cần thiết khi làm 1) và 3)
Rất mong admin gợi ý cho.
Xin cảm ơn.
Bạn có thể thử làm bản đơn giản hơn: tính tổng trọng số tối thiểu để 3 đỉnh cho trước liên thông. Bài này đơn giản hơn nhưng tư tưởng giống bài QBBUILD.
Với 3 hay 4 đỉnh thì em duyệt các cặp đỉnh i,j rồi lấy res=min(c[i,a]+c[i,b]+c[i,j]+c[j,c] (+c[j,d]) ) . nhưng với bài toán tương tự nhưng nhiều đỉnh hơn như NKBUILD thì em chưa làm được . Anh có thể gợi ý ko ạ :3
Bài NKBUILD dùng qhd theo kiểu f(u, S) = chi phí nhỏ nhất nếu mình đã nối được hết các đỉnh thuộc tập S, và trong khi nối thì mình có đi qua đỉnh u.
Có 2 vấn đề khó nhất:
