1584. Min Cost to Connect All Points

题目信息

题号:

1584

难度:

Medium

主题:

图、最小生成树、曼哈顿距离

原题:

LeetCode 1584

重点:

两点连边成本为曼哈顿距离;选择总成本最小的边集,使任意两点之间存在唯一简单路径

题目重述

给定平面点数组 points。连接两点 [x_i,y_i] 与 [x_j,y_j] 的成本为 |x_i-x_j| + |y_i-y_j|。

请选择若干连接,使全部点连通,并且任意两点之间恰好存在一条简单路径。返回最小总成本。

1 <= points.length <= 1000,坐标位于 [-10^6,10^6],所有点互不相同。

自建示例

沿较短边连接可形成最小生成树:

输入:points = [[0,0],[2,0],[2,2]]
输出:4
解释:连接前两点成本 2,再连接后两点成本 2,总计 4。

单个点无需任何连接:

输入:points = [[5,5]]
输出:0
解释:一个点本身已经连通。