文章
1
粉丝
0
获赞
1
访问
550
kruskal算法套用
#include<bits/stdc++.h>
using namespace std;
struct node{
double x,y;
}vec[105];
struct edg{
int u,v;
double len;
}edge[100*50];
int fa[105];
bool cmp(edg a,edg b){
return a.len<b.len;
}
int find(int x){
if(fa[x]==x)
return x;
fa[x]=find(fa[x]);
return fa[x];
}
int main(){
int n;
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>vec[i].x>>vec[i].y;
fa[i]=i;
}
int len=n*(n-1)/2;
int cnt=0;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].len=sqrt(pow((vec[i].x-vec[j].x),2)+pow((vec[i].y-vec[j].y),2));
}
}
sort(edge,edge+len,cmp);
int sum=0;
double res=0;
for(int i=0;i<len;i++){
int fu=find(edge[i].u);
int fv...
登录后发布评论
暂无评论,来抢沙发