作者：郎郎2502918483 | 来源：互联网 | 2023-12-14 12:55
给定一个二维平面上的一些点，通过计算曼哈顿距离，求连接所有点的最小总费用。只有任意两点之间有且仅有一条简单路径时，才认为所有点都已连接。给出了几个示例并给出了对应的输出。
- 连接所有点的最小费用
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例 1：
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：
输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
示例 3：
输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
示例 4：
输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
示例 5：
输入：points = [[0,0]]
输出：0
提示：
1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。
点击查看代码
class Solution {
public:
int fa[2000],n,tot=0;
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
bool iscomb(int x,int y){
int u,v;
u=find(x);
v=find(y);
if(u!=v){
fa[v]=u;
return 1;
}
return 0;
}
struct BIAN{
int from,to;
int len;
}tbian[500600];
static bool cmp(BIAN x,BIAN y){
return x.len }
int kruskal(){
int cost=0;
sort(tbian,tbian+tot,cmp);
for(int i=0;i for(int i=0;i if(iscomb(tbian[i].from,tbian[i].to)) cost+=tbian[i].len;
}
return cost;
}
int minCostConnectPoints(vector>& points) {
int i,j;
n=points.size();
for(i=0;i for(j=i+1;j tbian[tot].from=i;
tbian[tot].to=j;
tbian[tot].len=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]);
tot++;
}
}
return kruskal();
}
};
京公网安备 11010802041100号