Editorial for Educational Backtracking: Đi dạo


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gọi ~w(x,y)~ là độ dài cạnh từ x đến y.

Ta duyệt để cố định ~\frac{k}{2}-1~ đỉnh ở vị trí lẻ (đỉnh còn lại là ~1~).

Với mỗi cặp đỉnh lẻ cạnh nhau ~x~, ~y~, tìm ~k-2~ đỉnh ~u~ thỏa mãn ~w(x,u) + w(u,y)~ ngắn nhất. Loại bỏ các đỉnh thuộc tập đỉnh lẻ, ta còn ít nhất ~\frac{k}{2}~ đỉnh. Sau đó ta giữ lại đúng ~\frac{k}{2}~ đỉnh có ~w(x,u) + w(u,y)~ ngắn nhất. Cuối cùng, ta duyệt để tìm ra tập ~\frac{k}{2}~ đỉnh tại các vị trí lẻ.

Độ phức tạp: ~O(n^k)~, ~T(n^{\frac{k}{2}-1}*\frac{k}{2}^{\frac{k}{2}})~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.