举杯消愁愁更愁,月底账单入水流 • 7个月前
#include<bits/stdc++.h>
using namespace std;
int n;
struct city{
int x,y;
}c[5005];
struct road{
float len; //路的长度
int a,b; //连接的两个城市的编号
}r[10000];
int group[100005]; //连通分量看作一组组 group[i]的值表示编号为i的节点属于那个连通分量
int find(int x){ //并查集 查连通分量编号
if(x!=group[x]){ //并不是自己的编号
group[x]=find(group[x]); //去查与自己连通的编号
}
return group[x];
}
float far(city a,city b){
return sqrt(pow(abs(a.x-b.x),2)+pow(abs(a.y-b.y),2));
}
bool cmp(road x,road y){
if(x.len!=y.len) return x.len<y.len;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i].x,&c[i].y);
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
r[cnt].a=i;
r[cnt].b=j;
r[cnt].len=far(c[i],c[j]); //初始化r数组
cnt++; //cnt统计道路数量
}
}
float ans=0;
for(int i=1;i<=n;i++){
group[i]=i; //初始编号为自身
}
sort(r,r+cnt,cmp); //长短从小到大
for(int i=0;i<cnt;i++){
if(find(r[i].a)!=find(r[i].b)){ //两边端点不同
ans+=r[i].len;
group[find(r[i].a)]=find(r[i].b);
}
}
printf("%.2f",ans);
return 0;
}
评论:
请先登录,才能进行评论