Chỉnh Sửa Tình Bạn

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

1. 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.

2. DP: $dp[\text{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: $dp[\text{mask}]={min}_{S\subseteq \text{mask}}(dp[\text{mask}⧵S]+\text{flip}[S])$

3. 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·2^N)$
• Bộ nhớ: $O(2^N)$