Hướng dẫn giải của Chọn Đoạn Không Giao

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ọn Đoạn Không Giao

Hướng tiếp cận

Bài toán tương đương với tìm tập độc lập lớn nhất trong đồ thị giao nhau của các đoạn thẳng. Vì đồ thị này là đồ thị hai phía, ta dùng định lý König.

Nhận xét quan trọng

Không có hai đoạn ngang nào giao nhau, và không có hai đoạn dọc nào giao nhau.
Giao nhau chỉ xảy ra giữa đoạn ngang và đoạn dọc → đồ thị giao nhau là đồ thị hai phía.
Theo định lý König: Tập độc lập lớn nhất = $N$ - Ghép cặp cực đại.

Thuật toán

Phân loại $N$ đoạn thành ngang và dọc.
Xây đồ thị hai phía: đoạn ngang ở bên trái, đoạn dọc ở bên phải, có cạnh nếu chúng giao nhau.
Kiểm tra giao nhau: đoạn ngang $(x_{1}, y) \to (x_{2}, y)$ giao đoạn dọc $(x, y_{1}) \to (x, y_{2})$ khi $x_{1} \leq x \leq x_{2}$ và $y_{1} \leq y \leq y_{2}$ .
Tìm ghép cặp cực đại bằng thuật toán Hungary (augmenting path).
Kết quả: $N$ - ghép cặp cực đại.

Độ phức tạp

Thời gian: $O (N^{3})$ (Hungary trên đồ thị hai phía $N$ đỉnh)
Bộ nhớ: $O (N^{2})$

Bình luận

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