题目描述

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

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

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

样例

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

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

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

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

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

提示：

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

算法分析

最小生成树

题目要求求所有点连接的最小总费用，即求该图的最小生成树，在选择prim算法还是kruskal算法时，需要考虑点和边的关系，题目给定的是n个点，每两个点之间都有一个哈密顿距离的权值，因此是一个稠密图求最小生成树问题，因此使用prim算法

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static int n;
    static int N = 1010;
    static int[][] g = new int[N][N];
    static int INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];
    static int prim()
    {
        Arrays.fill(dist, INF);
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            int t = -1;
            for(int j = 0;j < n;j ++)
            {
                if(!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;
            }
            st[t] = true;

            if(i != 0) res += dist[t];

            for(int j = 0;j < n;j ++)
            {
                dist[j] = Math.min(dist[j], g[t][j]);
            }
        }
        return res;
    }
    public int minCostConnectPoints(int[][] points) {
        n = points.length;
        for(int i = 0;i <= n;i ++) Arrays.fill(g[i], INF);
        Arrays.fill(st, false);
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < n;j ++)
            {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                g[i][j] = g[j][i] = Math.abs(x1 - x2) + Math.abs(y1 - y2);
            }

        int t = prim();

        return t;
    }
}