Hướng dẫn giải của Chỉnh Sửa Tình Bạn

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.

Tác giả: huunguyen

Lời giải: Chỉnh Sửa Tình Bạn

Hướng tiếp cận

Quy hoạch động trên bitmask, phân hoạch đỉnh thành các clique.

Nhận xét quan trọng

Tính chất yêu cầu tương đương với: trong đồ thị phần bù, nếu không có cạnh giữa $(A, B)$ và $(B, C)$ , thì không thể có cạnh $(A, C)$ . Điều này có nghĩa mỗi thành phần liên thông trong đồ thị thỏa mãn phải là một clique (đồ thị đầy đủ).

Do đó, bài toán quy về: phân hoạch $N$ đỉnh thành các clique sao cho tổng số cạnh cần thêm/xóa là nhỏ nhất.

Thuật toán

Tiền xử lý: Với mỗi tập con $S$ (bitmask), tính flip[S] = số cạnh cần thay đổi nếu $S$ thành clique.
DP: $d p [mask]$ = chi phí tối thiểu để phân hoạch các đỉnh trong mask thành các clique.
- Chuyển trạng thái: $d p [mask] = {min}_{S \subseteq mask} (d p [mask ⧵ S] + flip [S])$
Duyệt tất cả tập con của mask bằng kỹ thuật subset enumeration.

Độ phức tạp

Thời gian: $O (3^{N} + N^{2} \cdot 2^{N})$
Bộ nhớ: $O (2^{N})$

Bình luận

Không có bình luận tại thời điểm này.