LeetCode 1584. 连接所有点的最小费用
目录
题目描述
题意分析
平面上给定
n个整数坐标点，连接两点的代价是它们的曼哈顿距离（横坐标差的绝对值加纵坐标差的绝对值）。要让所有点两两连通，求所需的最小总代价。「使所有点连通」加上「代价最小」这两个条件合起来决定了答案的形态：最终选出的边一定构成一棵树。多一条边就会形成环，而环上任何一条边删掉后连通性不变、代价却更低；少一条边则连不通。所以恰好要选
n - 1条边。任意两点之间都可以直接连线，也就是说这是一张完全图，边数是 $\binom{n}{2}$ 约等于 $n^2 / 2$ 条。这个信息很关键——边不是稀疏给出的，而是稠密的、隐含的，甚至不需要真的建出来，任何两点的代价都能 $O(1)$ 现算。
n的上界是 1000，所以 $n^2 = 10^6$ 完全可以接受，而 $n^2 \log n$ 也不算过分。稠密图加上这个规模，正好落在「按点推进」这类做法的舒适区里；反过来，如果先把 $5 \times 10^5$ 条边全部建出来再排序，内存和常数都会明显吃紧。坐标范围是 $[-10^6, 10^6]$，单条边的代价最大约 $4 \times 10^6$，总代价最大约 $4 \times 10^9$——这超过了
int的上限。不过实际最小生成树的总权远小于这个悲观上界，题目也保证答案在int范围内，但初始化「无穷大」时必须留出余量，不能直接用Integer.MAX_VALUE。边界上
n = 1时不需要连任何边，答案是 0。
解法：Prim 最小生成树
核心思路
点之间构成隐式完全图。Kruskal 需要生成并排序 $O(n^2)$ 条边，时间为 $O(n^2\log n)$、空间为 $O(n^2)$；这里边权可以随时计算，使用数组版 Prim 更适合稠密图，只需 $O(n)$ 额外空间。
维护
inMst和minDist[v]：后者表示点v到当前已选点集合的最小边权。每轮在线性扫描中选择树外minDist最小的点u，把该边权计入答案，再用u更新其余点的最小连接代价。不变量：已选边连接所有
inMst中的点，且可以扩展成某棵最小生成树；对每个树外点，minDist是它到当前树的最小距离。正确性：当前树与树外点形成一个割，所选
u对应的是跨越该割的最小边。根据最小生成树的割性质，这条边是安全边，加入后仍存在包含当前已选边的最小生成树。距离更新又恢复第二个不变量。执行n轮后所有点连通，所选安全边构成最小生成树。
解题步骤
- 将所有
minDist初始化为无穷，设置minDist[0]=0。- 重复
n次：在线性扫描中找出尚未加入且minDist最小的点u。- 将
u加入生成树，并把minDist[u]累加到答案。- 现场计算
u到每个树外点的曼哈顿距离，取较小值更新minDist。样例
[[0,0],[2,2],[3,10],[5,2],[7,0]]依次加入的连接代价可为0,4,3,4,9，总费用 20。单点输入无需任何边，第一轮只累加初始化的 0。若更新时直接覆盖
minDist而不取最小值，已发现的更便宜连接会丢失。
代码实现
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
int[] minDist = new int[n];
boolean[] inMst = new boolean[n];
int inf = Integer.MAX_VALUE / 4;
for (int i = 0; i < n; i++) {
minDist[i] = inf;
}
minDist[0] = 0;
int answer = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!inMst[j] && (u == -1 || minDist[j] < minDist[u])) {
u = j;
}
}
inMst[u] = true;
answer += minDist[u];
for (int v = 0; v < n; v++) {
if (inMst[v]) {
continue;
}
int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (d < minDist[v]) {
minDist[v] = d;
}
}
}
return answer;
}
}
func minCostConnectPoints(points [][]int) int {
n := len(points)
inf := int(^uint(0) >> 1)
minDist := make([]int, n)
inMst := make([]bool, n)
for i := 0; i < n; i++ {
minDist[i] = inf / 4
}
minDist[0] = 0
answer := 0
for i := 0; i < n; i++ {
u := -1
for j := 0; j < n; j++ {
if inMst[j] {
continue
}
if u == -1 || minDist[j] < minDist[u] {
u = j
}
}
inMst[u] = true
answer += minDist[u]
for v := 0; v < n; v++ {
if inMst[v] {
continue
}
dx := points[u][0] - points[v][0]
if dx < 0 {
dx = -dx
}
dy := points[u][1] - points[v][1]
if dy < 0 {
dy = -dy
}
d := dx + dy
if d < minDist[v] {
minDist[v] = d
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2)$，每轮各进行一次选点扫描和距离更新扫描。
- 空间复杂度：$O(n)$，不显式保存完全图的边。
关键点总结
- 先识别最小生成树，再根据图的稠密程度选择实现。
- 完全图边权可现场计算，数组版 Prim 比物化所有边的 Kruskal 更省空间。
minDist[v]是点到整个已选集合的最短距离，不是到最近加入点的距离。- 每轮选择跨割最小边，正确性来自割性质。
- 第一轮加入起点并贡献 0，之后
n-1轮才对应真实边。
易错点总结
- 更新时直接覆盖
minDist：样例会丢掉旧的更便宜边，结果不再是 MST。- 只用起点更新一次：得到的是以起点为中心的星形树，样例费用会变成 31。
- 选点时不排除
inMst：会重复选择起点，无法扩展生成树。- 曼哈顿距离漏掉绝对值：
[[0,0],[2,2]]会产生负距离，正确费用是 4。- 外层只执行
n-1次：本实现第一轮仅选择零代价起点，会漏掉最后一个点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1135. 最低成本连通所有城市 | 中等 | 边由输入显式给出且可能不连通，需要判断无解并返回 -1 |
| 1168. 水资源分配优化 | 困难 | 打井成本要建模成通往虚拟源点的边，考的是建图技巧而非算法本身 |
| 1489. 找到最小生成树里的关键边和伪关键边 | 困难 | 需要逐边强制包含或排除后重跑，考察对生成树唯一性与权值相等的理解 |
| 547. 省份数量 | 中等 | 只求连通分量个数，无需权重，是并查集或搜索的入门形态 |
| 1319. 连通网络的操作次数 | 中等 | 边可重连而非新建，答案由连通分量数与冗余边数共同决定 |
| 684. 冗余连接 | 中等 | 反过来找出构成环的那条边，考的是并查集合并时的成环检测 |
| 743. 网络延迟时间 | 中等 | 目标是单源最短路而非连通总代价，松弛的是路径和而不是单边权重 |