跳到主要内容

LeetCode 1584. 连接所有点的最小费用

本节目标

按需计算曼哈顿距离，用 Prim 构造点集完全图的最小生成树。

这是最小生成树的 Prim 母题。任意两点之间的曼哈顿距离都是可选边，因此图是隐式完全图。

查看 LeetCode 原题

题意与约束​

连接所有二维点，连接 i、j 的代价为 |xi - xj| + |yi - yj|，求最小总费用。单点无需边，答案为 0。

直接思路与瓶颈​

枚举所有连接方式或所有生成树会随点数指数增长。也可以先显式生成完全图的 n² 条候选边再跑 Kruskal，但本题的边权可由坐标即时计算，提前存下所有边会额外占用 O(n²) 空间。应让已经接入的点集逐步向外扩张，只维护每个未接入点最便宜的一条接入边。

图模型与算法推导​

把每个坐标点视为顶点，任意两点之间都有一条权为曼哈顿距离的隐式边。added 是已经加入生成树的点集，minDist[v] 表示点 v 用一条边接到该集合的最小费用，而不是从固定起点到 v 的路径长度。每轮取未加入点中 minDist 最小者，代价累加后，用新点到所有剩余点的曼哈顿距离更新它们；这正是跨越当前切分的最轻边。

正确性依据​

初始任取一个点，令其接入代价为 0。循环开始时，对每个未加入点，minDist 都是它与 added 中任一点相连的最小边权；新加入点后扫描所有剩余点即可维持此不变量。取 minDist 最小的点，就是当前切分 added / V-added 上的最轻边终点。由切分性质，这条边可安全加入某棵最小生成树；加入后仍不会形成环，因为新点原本不在集合内。重复到所有点加入时，累计的安全边恰好形成一棵最小生成树。

样例执行过程​

输入 points=[[0,0],[2,2],[3,10],[5,2],[7,0]]，用下标 0..4 表示点。初始 added=∅，minDist=[0,∞,∞,∞,∞]，答案为 0。

  1. 选 0，added={0}，按曼哈顿距离更新为 minDist=[0,4,13,7,7]。
  2. 选 1（接入边权 4），added={0,1}，答案为 4；用点 1 更新后，minDist=[0,4,9,3,7]。
  3. 选 3（接入边权 3），added={0,1,3}，答案为 7；更新点 4 的最佳接入边为 4，得到 minDist=[0,4,9,3,4]。
  4. 选 4（接入边权 4），added={0,1,3,4}，答案为 11；点 2 的最小值仍为 9。
  5. 选 2（接入边权 9），added={0,1,2,3,4}，答案为 20。所有点已连接，返回 20。

代码实现​

不显式生成 n² 条边；每次选中一个点后才按需计算到其余点的距离。

C++17
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        const int n = points.size();
        const long long INF = 1LL << 60;
        vector<long long> minDist(n, INF);
        vector<bool> added(n, false);
        minDist[0] = 0;
        long long answer = 0;

        for (int round = 0; round < n; round++) {
            int vertex = -1;
            for (int candidate = 0; candidate < n; candidate++) {
                if (!added[candidate] &&
                    (vertex == -1 || minDist[candidate] < minDist[vertex])) {
                    vertex = candidate;
                }
            }
            added[vertex] = true;
            answer += minDist[vertex];

            for (int nxt = 0; nxt < n; nxt++) {
                long long weight =
                    abs(static_cast<long long>(points[vertex][0]) - points[nxt][0]) +
                    abs(static_cast<long long>(points[vertex][1]) - points[nxt][1]);
                minDist[nxt] = min(minDist[nxt], weight);
            }
        }
        return static_cast<int>(answer);
    }
};

复杂度分析​

共 n 轮，每轮选点与更新各扫描 n 个点，时间 O(n²)；minDist 和标记数组使用 O(n) 额外空间。

边界与易错点​

  • 初始化一个点的 minDist 为 0，它不应额外付接入成本。
  • 更新的是“到已选集合的最小单边费用”，不是路径和。
  • 选中点后再更新剩余点，不能重复把已选点加入答案。
  • 坐标可为负，曼哈顿距离必须取绝对值。

模式迁移​

当图由所有点对的可计算代价构成时，优先考虑按需 Prim；若边已显式列出并且数量可控，Kruskal 通常更直接。