分析
-
首先要把二维点变成一维点,可以使用哈希表
-
然后把一维点间的边的关系确定,用结构体存储点边间的关系
-
然后kruskal求最小生成树。
C++ 代码
class Solution {
public:
unordered_map<int,vector<int>> mp; //把二维变一维,方便进行图论操作
int n,m,ans,fa[1010];
struct point{ //结构体存储点边的关系
int a,b,d;
};
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
bool static cmp(point& a,point& b) //排序函数
{
return a.d<b.d;
}
int kruskal(vector<point> &v)
{
sort(v.begin(),v.end(),cmp); //先把所有点边关系按边权大小排序
for(int i=0;i<m;i++)
{
int a=v[i].a,b=v[i].b,w=v[i].d;
int faa=find(a),fbb=find(b);
if(faa!=fbb) //进行并查集操作
{
fa[faa]=fbb;
ans+=w;
}
}
return ans;
}
int minCostConnectPoints(vector<vector<int>>& points) {
n=points.size();
for(int i=0;i<n;i++)
{
mp[i]=points[i]; //哈希表建立映射关系
}
for(int i=0;i<n;i++) fa[i]=i;
vector<point> v;
for(int i=0;i<n;i++) //把每两点之间的距离都存入到数组v中
{
for(int j=i+1;j<n;j++)
{
int d=abs(mp[i][0]-mp[j][0])+abs(mp[i][1]-mp[j][1]);
v.push_back({i,j,d});
}
}
m=v.size(); //总的边数
return kruskal(v); //返回kruskal执行的结果
}
};