LeetCode 1584 Min Cost to Connect All Points
概述
https://leetcode.com/problems/min-cost-to-connect-all-points/
注意距离是曼哈顿距离。
很明显我们是要构建一棵树，因为有环的话是浪费行为。
我们可以一个节点一个节点地加，也可以从一个全连接图开始删。
Kruskal 最小生成树算法
我们先计算所有节点距离其他所有节点的距离矩阵。
起始时每个节点都是一棵树，我们找出最短距离，连接这两棵树，之后更新其他树对这棵树的距离， 重复操作直至我们就剩下了一棵树。
在这个过程中我们需要判断节点是否已经属于图中。
所以我们要用并查集算法吗？没必要，这里就一个图而已，直接数组标记不香吗？
笑死，谁说就一个图的？过程中还是有多个的。
class Solution {
public:
vector<int> p;
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
for (int i = 0; i < n; i ++) {
p.push_back(i);
}
vector<array<int, 3>> edges;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
edges.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j}); // d, i, j
}
}
int cost = 0;
make_heap(edges.begin(), edges.end(), greater<array<int, 3>>());
int count = 1;
while (!edges.empty()) {
pop_heap(edges.begin(), edges.end(), greater<array<int, 3>>());
auto e = edges.back();
edges.pop_back();
if (find(e[1]) == find(e[2])) continue;
cost += e[0];
count++;
if (count == n) break;
unite(e[1], e[2]);
}
return cost;
}
void unite(int i, int j) {
int pi = find(i);
int pj = find(j);
p[pi] = pj;
}
int find(int i) {
while (i != p[i]) {
p[i] = p[p[i]];
i = p[i];
}
return i;
}
};
然后就 TLE 了，因为时间复杂度 O(n^2logn^2)。
Kruskal 最小生成树算法（最小堆 + 早停）
Kruskal involves min heap to pick the smallest edge, and union-find to check if the edge is redundant. We exit when all points are connected.
make_heap 时间复杂度 O(n)，pop_heap() 时间复杂度 O(logn)。
早停是指当我们已经找到最小生成树的所有边时就没必要再迭代下去了。
class Solution {
public:
vector<int> p;
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
for (int i = 0; i < n; i ++) {
p.push_back(i);
}
vector<array<int, 3>> edges;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
edges.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j}); // d, i, j
}
}
int cost = 0;
make_heap(edges.begin(), edges.end(), greater<array<int, 3>>());
int count = 1;
while (!edges.empty()) {
pop_heap(edges.begin(), edges.end(), greater<array<int, 3>>());
auto e = edges.back();
edges.pop_back();
if (find(e[1]) == find(e[2])) continue;
cost += e[0];
count++;
if (count == n) break;
unite(e[1], e[2]);
}
return cost;
}
void unite(int i, int j) {
int pi = find(i);
int pj = find(j);
p[pi] = pj;
}
int find(int i) {
while (i != p[i]) {
p[i] = p[p[i]];
i = p[i];
}
return i;
}
};
Prim 最小生成树算法
https://labuladong.gitee.io/algo/2/19/41/
起始时随便选一个点作为我们最小生成树的起点，计算其横切边，注意我们用优先级序列维护横切边列表， 因为：
- 我们需要知道最小权重的横切边，因为其必然存在于最少生成树中，
- 横切边列表会随着算法进行
- 增加：新加入的节点带来了更多的横切边，
- 减少：新加入的节点同时使原本的一个横切边，
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size(), cost = 0, count = 1, c = 0; // c is the index of the current processing point
vector<bool> visited(n, false);
priority_queue<pair<int, int>> pq;
while (count < n) {
visited[c] = true;
// update cuts
for (int i = 0; i < n; i ++) {
if (!visited[i]) {
pq.push({-(abs(points[i][0] - points[c][0]) + abs(points[i][1] - points[c][1])), i});
}
}
while (visited[pq.top().second]) { // cause this edge may not be a cut now
pq.pop();
}
auto p = pq.top();
pq.pop();
count++;
cost -= p.first; // cause the weights we saved are negative
c = p.second;
}
return cost;
}
};