C++刷leetcode（1584. 连接所有点的最小费用）【kruskal算法】

糖逗

题目描述：

1. 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
   
2. 
   
3. 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
   
4. 
   
5. 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
    
14. 输出：20
    
15. 解释：
    
16. 
    
17. 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
    
18. 注意到任意两个点之间只有唯一一条路径互相到达。
    
19. 示例 2：
    
20. 
    
21. 输入：points = [[3,12],[-2,5],[-4,1]]
    
22. 输出：18
    
23. 示例 3：
    
24. 
    
25. 输入：points = [[0,0],[1,1],[1,0],[-1,1]]
    
26. 输出：4
    
27. 示例 4：
    
28. 
    
29. 输入：points = [[-1000000,-1000000],[1000000,1000000]]
    
30. 输出：4000000
    
31. 示例 5：
    
32. 
    
33. 输入：points = [[0,0]]
    
34. 输出：0
    
35.  
    
36. 
    
37. 提示：
    
38. 
    
39. 1 <= points.length <= 1000
    
40. -106&#160;<= xi, yi <= 106
    
41. 所有点&#160;(xi, yi)&#160;两两不同。
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     vector<int> father;
   
4. public:
   
5.     struct Edge{
   
6.         int a1, a2, distance;
   
7.         bool operator < (const Edge & other) const{
   
8.             return this -> distance < other.distance;
   
9.         }
   
10.     };  
    
11.     int find_root(int a){
    
12.         if(father[a] != a)return find_root(father[a]);
    
13.         return a;
    
14.     }
    
15.     void unite(int a, int b){
    
16.         int temp1 = find_root(a);
    
17.         int temp2 = find_root(b);
    
18.         if(temp1 != temp2){
    
19.             father[temp1] = temp2;
    
20.         }
    
21.         return;
    
22.     }
    
23. 
    
24.     int solution(int len, vector<Edge>& store){
    
25.         //建立父亲集合
    
26.         father = vector<int>(len, 0);
    
27.         for(int i = 0; i < len; i++){
    
28.             father[i] = i;
    
29.         }
    
30.         int res = 0;
    
31.         for(auto cha : store){
    
32.             int temp1 = find_root(cha.a1);
    
33.             int temp2 = find_root(cha.a2);
    
34.             if(temp1 != temp2){
    
35.                 res += cha.distance;
    
36.                 unite(temp1, temp2);
    
37.                 len--;//当所有点都在一棵树的时候停止
    
38.                 if(len == 1)return res;
    
39.             }
    
40.         }
    
41.         return res;
    
42.     }
    
43.     int minCostConnectPoints(vector<vector<int>>& points) {
    
44.         int len = points.size();
    
45.         vector<Edge> store;
    
46.         for(int i = 0; i < len; i++){
    
47.             for(int j = i; j < len; j++){
    
48.                 store.push_back({i, j,
    
49.                 abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
    
50.             }
    
51.         }
    
52.         sort(store.begin(), store.end());
    
53.         return solution(len, store);
    
54.     }
    
55. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ie-da-by-yizhe-shi/
学习视频：https://www.bilibili.com/video/B ... 3053730826471308736