Hướng dẫn cho HackDream Purple 05-E: Xây Dựng Đế Chế


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: tuntun

Subtask 1

Ta sẽ duyệt từng cạnh để thay đổi. Với mỗi cạnh thay đổi, ta chọn ~2~ đỉnh của ~2~ thành phần liên thông mới và nối lại. Từ đó tính tổng khoảng cách ứng với cách thay đổi đó. ĐPT: ~O(N^4)~ hoặc ~O(N^4 \times log(N))~.

Subtask 2, 3, 4 đều dùng nhận xét quan trọng: Với mỗi cạnh bị thay đổi, số lần đi qua cạnh mới luôn giữ nguyên, vì vậy ~2~ đỉnh ~u, v~ mới được chọn để nối vào cần đảm bảo tổng đường đi từ đỉnh trong thành phần liên thông của u đến u và tổng đường đi từ đỉnh trong thành phần liên thông của v đến v là bé nhất.

Subtask 2

Duyệt cạnh để xóa, sau đó với mỗi thành phần liên thông, dfs từ tất cả các đỉnh để tìm đỉnh tối ưu nhất. ĐPT: ~O(N^3)~.

Subtask 3

Với đồ thị đường thẳng và trọng số bằng ~1~, khi ta xóa ~1~ cạnh, ta sẽ xác định được ~2~ đỉnh cần nối là ~2~ đỉnh nằm giữa của ~2~ đoạn bị chia ra. Sử dụng mảng cộng dồn hoặc hai con trỏ để tính chi phí. ĐPT: ~O(N^2)~.

Subtask 4

Cải tiến từ sub2, sau khi xóa ~1~ cạnh, ta có thể tính chi phí tối ưu nhất bằng cách sử dụng reroot dp. Giả sử khi ta có chi phí tại đỉnh ~a~, ta có thể tính chi phí của các đỉnh ~b~ kề với ~a~ như sau: ~cost_b = cost_a - sz_b * w + (S - sz_b) * w~ (với ~cost_x~ là chi phí tại ~x~, ~sz_x~ là số node trong cây con gốc ~x~, ~w~ là trọng số cạnh ~(a, b)~, ~S~ là tổng số đỉnh trong thành phần liên thông đó). ĐPT: ~O(N^2)~.


Bình luận

Không có bình luận nào.