1584. Min Cost to Connect All Points [Medium]

https://leetcode.com/problems/min-cost-to-connect-all-points/

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

Example 3:

Input: points = [[0,0],[1,1],[1,0],[-1,1]] Output: 4

Example 4:

Input: points = [[-1000000,-1000000],[1000000,1000000]] Output: 4000000

Example 5:

Input: points = [[0,0]] Output: 0

Constraints:

1 <= points.length <= 1000-106 <= xi, yi <= 106All pairs (xi, yi) are distinct.

---

算法思路：

方法1：prim

方法2：kruskal

// Runtime: 140 ms, faster than 89.21% class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { int n = points.size(); vector<vector<int>> g(n, vector<int>(n, INT_MAX)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) g[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]); } } return prim(g); } private: int prim(const vector<vector<int>>& g) { int n = g.size(); vector<int> dist(n, INT_MAX); // vector<int> parent(n, -1); // 本题不需要生成树路径，因此parent可以不写 int cost = 0; int count = 0; // 初始化 for (int w = 0; w < n; w++) { dist[w] = g[0][w]; } dist[0] = 0; count++; // 生成树生长 while (1) { int v = findMinDist(g, dist); // 找到未收录的点v，其dist[v]最小 if (v == -1) break; // 没找到，说明已经没了可选的点了 cost += dist[v]; // 收录进来的花费 dist[v] = 0; // 收录进来 count++; for (int w = 0; w < n; w++) { // 更新 if (dist[w] != 0 && g[v][w] < dist[w]) { dist[w] = g[v][w]; } } } if (count == n) return cost; return -1; // 最小生成树没有收录n个点，说明测试案例有问题 } int findMinDist(const vector<vector<int>>& g, const vector<int>& dist) { int minV = -1; int minDist = INT_MAX; int n = g.size(); for (int v = 0; v < n; v++) { if (dist[v] != 0 && dist[v] < minDist) { minV = v; minDist = dist[v]; } } return minV; } };

 

// Runtime: 580 ms, faster than 62.33% // priority_queue< pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; // 太长了，看的头晕，改造下，如下所示： // priority_queue<Pipii, Vpipii, Greater> pq; #define Pipii pair<int, pair<int, int>> #define Vpipii vector<pair<int, pair<int, int>>> #define Greater greater<pair<int, pair<int, int>>> class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { int n = points.size(); priority_queue<Pipii, Vpipii, Greater> pq; // 小顶堆 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]); pq.push({cost, {i, j}}); } } return kruskal(pq, n - 1); } private: int kruskal(priority_queue<Pipii, Vpipii, Greater>& pq, const int& cnt) { vector<int> s(cnt + 1, -1); int count = 0; int res = 0; int cost, u, v; while (count < cnt) { auto pp = pq.top(); pq.pop(); cost = pp.first; u = pp.second.first; v = pp.second.second; if (myUnion(s, u, v)) { count++; res += cost; } } return res; } bool myUnion(vector<int>& s, int u, int v) { int root1 = myFind(s, u); int root2 = myFind(s, v); if (root1 == root2) return false; if (s[root1] < s[root2]) { s[root1] += s[root2]; s[root2] = root1; } else { s[root2] += s[root1]; s[root1] = root2; } return true; } int myFind(vector<int>& s, int x) { if (s[x] < 0) { return x; } else { return s[x] = myFind(s, s[x]); } } };