社区讨论
【求助】最小生成树(克鲁斯卡尔)只得了60分。
P1433吃奶酪参与者 9已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi4ed333
- 此快照首次捕获于
- 2025/11/18 17:54 4 个月前
- 此快照最后确认于
- 2025/11/18 17:58 4 个月前
第一个和倒数三个点WA。
CPP#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double tot; //存总距离;
int n,k,f[151];
double zuobiao[151][2],minn=10000000; //minn为从(0,0)到最近点的距离。
struct hehe
{
int x,y; //x号点和y号点的距离为v;
double v;
}a[22510];
bool comp(hehe q,hehe p) //排序;
{
return q.v<p.v;
}
int father(int q) //找父亲;
{
if(q!=f[q]) f[q]=father(f[q]);
return f[q];
}
void unionn(int q,int p) //合并;
{
int la=f[q],lb=f[p];
if(la!=lb) f[la]=lb;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&zuobiao[i][0],&zuobiao[i][1]); //输入坐标;
f[i]=i; //初始化父亲为自己;
if(sqrt((pow(zuobiao[i][0],2))+(pow(zuobiao[i][1],2)))<minn) minn=sqrt((pow(zuobiao[i][0],2))+(pow(zuobiao[i][1],2)));
//计算(0,0)到最近点距离
}
for(int i=1;i<=n;i++) // i号点到j号点的距离;
for(int j=1;j<=n;j++)
if(i==j) a[(i-1)*n+j].v=100000000; //i,j相同时赋极大值;
else
{
a[(i-1)*n+j].x=i;
a[(i-1)*n+j].y=j;
a[(i-1)*n+j].v=sqrt(1.0*(pow(zuobiao[i][0]-zuobiao[j][0],2)+pow(zuobiao[i][1]-zuobiao[j][1],2)));
}
sort(a+1,a+n*n+1,comp);
for(int i=1;i<=n*n;i++)
{
if(father(a[i].x)!=father(a[i].y))
{
unionn(a[i].x,a[i].y);
tot+=a[i].v;
k++;
}
if(k==n-1) break;
}
tot+=minn; //连接(0,0);
printf("%.2lf",tot);
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...