连接所有点的最小费用 图解题解

这道题到底在问什么

输入

points=[[0,0],[2,2],[3,10],[5,2],[7,0]]

输出

20

最优解：一步一步想明白

1. 3记住这一句，下面每条边都在套它。
2. 4起手：5 个点各自孤立，一条边都还没选（费用 0）。下面把「所有点对」按曼哈顿距离从小到大排好，逐条尝试连接。
3. 5看边 P1-P3：曼哈顿距离 = |2-5| + |2-2| = 3。这是当前最短的可用边，查两端的根——
4. 6根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +3 = 3。已选 1/4 条。
5. 7看边 P0-P1：曼哈顿距离 = |0-2| + |0-2| = 4。这是当前最短的可用边，查两端的根——
6. 8根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +4 = 7。已选 2/4 条。
7. 9看边 P3-P4：曼哈顿距离 = |5-7| + |2-0| = 4。这是当前最短的可用边，查两端的根——
8. 10根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +4 = 11。已选 3/4 条。
9. 11看边 P0-P3：曼哈顿距离 = |0-5| + |0-2| = 7。先查根——
10. 12P0、P3 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
11. 13看边 P0-P4：曼哈顿距离 = |0-7| + |0-0| = 7。先查根——
12. 14P0、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
13. 15看边 P1-P4：曼哈顿距离 = |2-7| + |2-0| = 7。先查根——
14. 16P1、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
15. 17看边 P1-P2：曼哈顿距离 = |2-3| + |2-10| = 9。这是当前最短的可用边，查两端的根——
16. 18根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +9 = 20。已选 4/4 条。
17. 19看边 P2-P3：曼哈顿距离 = |3-5| + |10-2| = 10。先查根——
18. 20P2、P3 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
19. 21看边 P0-P2：曼哈顿距离 = |0-3| + |0-10| = 13。先查根——
20. 22P0、P2 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
21. 23看边 P2-P4：曼哈顿距离 = |3-7| + |10-0| = 14。先查根——
22. 24P2、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
23. 25选满 4 条边，所有点连成一棵树（同一组同色）。最小总费用 = 20。这就是答案。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

import java.util.*;
class Solution {
    int[] parent;
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int w = Math.abs(points[i][0] - points[j][0])
                      + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{w, i, j});
            }
        edges.sort((a, b) -> a[0] - b[0]);
        int cost = 0, used = 0;
        for (int[] e : edges) {
            int ra = find(e[1]), rb = find(e[2]);
            if (ra != rb) { parent[rb] = ra; cost += e[0]; used++; }
            if (used == n - 1) break;
        }
        return cost;
    }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                w = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((w, i, j))
        edges.sort()
        cost = used = 0
        for w, i, j in edges:
            ri, rj = find(i), find(j)
            if ri != rj:
                parent[rj] = ri
                cost += w
                used += 1
                if used == n - 1:
                    break
        return cost

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
        vector<array<int,3>> edges;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int w = abs(points[i][0] - points[j][0])
                      + abs(points[i][1] - points[j][1]);
                edges.push_back({w, i, j});
            }
        sort(edges.begin(), edges.end());
        int cost = 0, used = 0;
        for (auto& e : edges) {
            int ra = find(e[1]), rb = find(e[2]);
            if (ra != rb) { parent[rb] = ra; cost += e[0]; used++; }
            if (used == n - 1) break;
        }
        return cost;
    }
};

复杂度

面试官可能追问