# 1584. Min Cost to Connect All Points ## Tóm tắt đề Cho $n$ điểm trên mặt phẳng. Chi phí để nối các điểm tính theo khoảng cách Manhattan, $f(a, b) = |a_x - b_x| + |a_y - b_y|$. Tìm chi phí nhỏ nhất để nối tất cả các điểm với nhau. ## Giới hạn $1 \le n \le 1000$ ## Lời giải Đây là bài toán MST cổ điển, có thể giải bằng các thuật toán: - Thuật toán Prim trong $O(V^2)$, tốt với đồ thị đặc. - Thuật toán Kruskal trong $O(E \log E)$, tốt với đồ thị thưa. Ở đây, đồ thị là đầy đủ, mỗi cặp đỉnh được nối với nhau, nên ta có $E = O(V^2)$, do đó sử dụng thuật toán Prim sẽ nhanh hơn. Tuy nhiên trong lời giải mình sử dụng Kruskal. Về thuật toán Kruskal, mọi người đã học trong môn Toán rời rạc rồi. Sắp xếp các cạnh theo trọng số, và duyệt từng cạnh theo trọng số tăng dần, nếu nối mà có thể giảm số thành phần liên thông thì ta nối. Trong lời giải của mình sử dụng `priority_queue`. Để xử lí việc nối các đỉnh và kiểm tra thành phần liên thông, ta sử dụng Disjoint Set Union (DSU) có 3 phương thức: - `find(x)` để tìm đỉnh đại diện của thành phần liên thông chứa `x`. - `merge(x, y)` để nối thành phần liên thông chứa 2 đỉnh `x` và `y`. - `same(x, y)` để kiểm tra xem `x` và `y` có cùng thuộc thành phần liên thông hay không. Nếu DSU được tối ưu đúng cách (sử dụng Path Compression và Union by Rank), các thao tác trên có thể coi như $O(1)$. Độ phức tạp của lời giải theo đó là độ phức tạp của thuật toán MST, là $O(n^2)$ với Prim hoặc $O(n^2 \log n^2)$ với Kruskal. ## Bonus Ta đặt ra một câu hỏi: có nhất thiết phải lấy tất cả các cặp đỉnh không? Trên thực tế, bài toán này có thể giải được với $n \le 10^5$ hoặc hơn. Ý tưởng là khi số cặp đỉnh phải xét chỉ là $O(n)$ thì ta có thể dùng Kruskal để tìm MST trong $O(n \log n)$. Với mỗi 1 đỉnh, ta xét các góc phần 8, và với mỗi góc phần 8, ta nối đỉnh đó với đỉnh gần nhất. Nên số cạnh cần xét chỉ là $O(n)$. Để tìm được những điểm này, ta có thể sử dụng thuật toán Đường quét (Sweep Line). Chi tiết trong phần tham khảo. ## Tham khảo 1. https://cp-algorithms.com/data_structures/disjoint_set_union.html#time-complexity - phân tích độ phức tạp của DSU. 2. https://leetcode.com/problems/min-cost-to-connect-all-points/submissions/1049846332/ - lời giải của mình 3. https://vnoi.info/wiki/algo/geometry/Sweep-Line.md - lời giải cho bài này với độ phức tạp $O(n \log n)$.