LeetCode：1584. Min Cost to Connect All Points连接所有点的最小费用（C语言）

落日映苍穹つ 2023-01-08 05:19 95阅读 0赞

**题目描述：**  
给你一个points 数组，表示 2D 平面上的一些点，其中 points\[i\] = \[xi, yi\] 。

连接点 \[xi, yi\] 和点 \[xj, yj\] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：  
![在这里插入图片描述][1a89c19ffd7d98b7da9483b88a8b41fa.png_pic_center]

输入：points = \[\[0,0\],\[2,2\],\[3,10\],\[5,2\],\[7,0\]\]  
输出：20  
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。  
注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：  
![在这里插入图片描述][f93b1e05075989ed5b9379b345f4d324.png_pic_center]

输入：points = \[\[3,12\],\[-2,5\],\[-4,1\]\]  
输出：18

示例 3：

输入：points = \[\[0,0\],\[1,1\],\[1,0\],\[-1,1\]\]  
输出：4

示例 4：

输入：points = \[\[-1000000,-1000000\],\[1000000,1000000\]\]  
输出：4000000

示例 5：

输入：points = \[\[0,0\]\]  
输出：0

提示：

1 <= points.length <= 1000
    -106 <= xi, yi <= 106
    所有点 (xi, yi) 两两不同。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

void swap(int* a, int* b) { 
        int tmp = *a;
        *a = *b, *b = tmp;
    }
    
    struct Edge { 
        int len, x, y;
    };
    
    int cmp(struct Edge* a, struct Edge* b) { 
        return a->len - b->len;
    }
    
    int find(int* f, int x) { 
        return f[x] == x ? x : (f[x] = find(f, f[x]));
    }
    
    int unionSet(int* f, int* rank, int x, int y) { 
        int fx = find(f, x), fy = find(f, y);
        if (fx == fy) { 
            return false;
        }
        if (rank[fx] < rank[fy]) { 
            swap(&fx, &fy);
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
        return true;
    }
    
    int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize) { 
        int n = pointsSize;
        struct Edge edges[(n + 1) * n / 2];
        int edgesSize = 0;
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                edges[edgesSize].x = i;
                edges[edgesSize].y = j;
                edges[edgesSize++].len = fabs(points[i][0] - points[j][0]) + fabs(points[i][1] - points[j][1]);
            }
        }
        qsort(edges, edgesSize, sizeof(struct Edge), cmp);
        int f[n], rank[n];
        for (int i = 0; i < n; i++) { 
            f[i] = i;
            rank[i] = 1;
        }
        int ret = 0, num = 1;
        for (int i = 0; i < edgesSize; i++) { 
            if (unionSet(f, rank, edges[i].x, edges[i].y)) { 
                ret += edges[i].len;
                num++;
                if (num == n) { 
                    break;
                }
            }
        }
        return ret;
    }

**运行结果：**

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/min-cost-to-connect-all-points/solution/lian-jie-suo-you-dian-de-zui-xiao-fei-yo-kcx7/][https_leetcode-cn.com_problems_min-cost-to-connect-all-points_solution_lian-jie-suo-you-dian-de-zui-xiao-fei-yo-kcx7]

[1a89c19ffd7d98b7da9483b88a8b41fa.png_pic_center]: /images/20221119/27d02fdea9774dc2b2d34f7c65b1867c.png
[f93b1e05075989ed5b9379b345f4d324.png_pic_center]: /images/20221119/17e4eda6ede04b89bb289b01993b7fb4.png
[https_leetcode-cn.com_problems_min-cost-to-connect-all-points_solution_lian-jie-suo-you-dian-de-zui-xiao-fei-yo-kcx7]: https://leetcode-cn.com/problems/min-cost-to-connect-all-points/solution/lian-jie-suo-you-dian-de-zui-xiao-fei-yo-kcx7/