问题
给定一个二维数组points，其中points[i] = [xi, yi]表示平面上的一个点。
连接两个点[xi, yi]和[xj, yj]的费用为它们之间的曼哈顿距离：
|xi - xj| + |yi - yj|要求把所有点都连接起来，并且任意两个点之间都可以通过若干条边互相到达。返回连接所有点所需要的最小总费用。
示例 1：
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：用最小费用连接所有点，总费用为20。
示例 2：
输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
思路
首先这道题的直觉解法很明显：既然要让所有点都连通，那我们可以在点和点之间连边。任意两个点之间都能连一条边，边权就是它们的曼哈顿距离。
那问题就变成了：在一个完全图里，选择一些边，让所有点连通，并且总费用最小。
如果随便连边，很容易多连出一些没必要的边。因为只要所有点能互相到达就够了，不需要每两个点之间都直接连边。对于n个点来说，真正需要的边数其实是n - 1条。
那是不是可以把问题转化成“最小生成树”？也就是在所有能连接全部节点的方案中，找出边权总和最小的一棵树。
怎么构造这棵最小生成树？可以想到 Prim 算法。
Prim 的想法是：先从任意一个点开始，把它当成当前已经连好的树。然后每次从还没加入树的点里，选择一个“接入当前树代价最小”的点加入进来。不断重复，直到所有点都加入树。
拿变量来说，minDist[i]表示点i接入当前这棵树的最小费用。
一开始只有点0在树里，所以：
minDist[0] = 0 其他点 minDist = INT_MAX每次选出未访问点中minDist最小的那个点u，把它加入树，并把这次接入费用加到答案里。
那加入u后，为什么要更新其他点的minDist？
因为u成了树的一部分，其他还没加入树的点，现在除了可以通过原来的树中节点接入，也可以通过u接入。于是对每个未访问点x，计算u到x的曼哈顿距离，如果这个距离更小，就更新minDist[x]。
不难发现，这个过程就是一直选择当前最便宜的连接方式，把一个新点接入已经形成的树里。等所有点都加入后，得到的总费用就是最小连接费用。
解决
先定义几个关键变量。
minDist[i] 表示点 i 接入当前生成树的最小费用 visited[i] 表示点 i 是否已经加入生成树 res 表示当前总费用一开始选择点
0作为起点，所以设置：minDist[0] = 0循环
n次，每次向生成树中加入一个点。在所有还没访问过的点里，找到
minDist最小的点u：!visited[j] && minDist[j] 最小这个点就是当前接入生成树代价最小的点。
把点
u加入生成树。标记：
visited[u] = true并把它的接入费用加入答案：
res += minDist[u]更新其他未访问点的最小接入费用。
对于每个还没加入生成树的点
x，计算它和u之间的曼哈顿距离：abs(points[u][0] - points[x][0]) + abs(points[u][1] - points[x][1])如果通过
u接入更便宜，就更新minDist[x]。
注意：这里不需要提前把所有边存下来。因为任意两个点之间的距离都可以直接通过坐标计算出来，所以每次加入新点后，现场计算并更新即可。
classSolution{public:intminCostConnectPoints(vector<vector<int>>&points){intn=points.size();vector<int>minDist(n,INT_MAX);vector<bool>visited(n,false);intres=0;minDist[0]=0;for(inti=0;i<n;++i){intu=-1;for(intj=0;j<n;++j){if(!visited[j]&&(u==-1||minDist[j]<minDist[u])){u=j;}}visited[u]=true;res+=minDist[u];for(intx=0;x<n;++x){if(!visited[x]){intdist=abs(points[u][0]-points[x][0])+abs(points[u][1]-points[x][1]);if(minDist[x]>dist){minDist[x]=dist;}}}}returnres;}};时间复杂度为O(n^2)，因为每次选点需要遍历所有点，更新距离也需要遍历所有点；空间复杂度为O(n)，主要用于minDist和visited数组。
