C++刷leetcode（1584. 连接所有点的最小费用）【kruskal算法】
题目描述：给你一个points 数组，表示 2D 平面上的一些点，其中 points = 。
连接点 和点 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例 1：
输入：points = [,,,,]
输出：20
解释：
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：
输入：points = [,[-2,5],[-4,1]]
输出：18
示例 3：
输入：points = [,,,[-1,1]]
输出：4
示例 4：
输入：points = [[-1000000,-1000000],]
输出：4000000
示例 5：
输入：points = []
输出：0
提示：
1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
vector<int> father;
public:
struct Edge{
int a1, a2, distance;
bool operator < (const Edge & other) const{
return this -> distance < other.distance;
}
};
int find_root(int a){
if(father != a)return find_root(father);
return a;
}
void unite(int a, int b){
int temp1 = find_root(a);
int temp2 = find_root(b);
if(temp1 != temp2){
father = temp2;
}
return;
}
int solution(int len, vector<Edge>& store){
//建立父亲集合
father = vector<int>(len, 0);
for(int i = 0; i < len; i++){
father = i;
}
int res = 0;
for(auto cha : store){
int temp1 = find_root(cha.a1);
int temp2 = find_root(cha.a2);
if(temp1 != temp2){
res += cha.distance;
unite(temp1, temp2);
len--;//当所有点都在一棵树的时候停止
if(len == 1)return res;
}
}
return res;
}
int minCostConnectPoints(vector<vector<int>>& points) {
int len = points.size();
vector<Edge> store;
for(int i = 0; i < len; i++){
for(int j = i; j < len; j++){
store.push_back({i, j,
abs(points - points) + abs(points - points)});
}
}
sort(store.begin(), store.end());
return solution(len, store);
}
};
参考链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points/solution/c-kruskalprimsuan-fa-jie-da-by-yizhe-shi/
学习视频：https://www.bilibili.com/video/BV1Ev411q7gg?from=search&seid=3053730826471308736
页:
[1]