社区讨论

【求助】最小生成树(克鲁斯卡尔)只得了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 条回复,欢迎继续交流。

正在加载回复...