这个最小生成树哪一步不对

yueyufeng

#include<bits/stdc++.h>
using namespace std;
int n;
int f[1010];
struct dian{
        int x,y,h;
}DIAN[1010];
struct XIAN{
        int d1,d2;
        double ju;
}xian[100000];
double cmp(XIAN x1,XIAN x2){
        return x1.ju<x2.ju;
}
int find(int x){
          if(x==f[x])
          return x;
          return f[x]=find(f[x]);
}
void root(int d1,int d2){
        int xx=find(d1);
        int yy=find(d2);
         if(xx!=yy){
                 f[yy]=xx;
         }
}
int main(){
          cin>>n;
          int cnt=0;
          double w;
          for(int i=0;i<n;i++){
                  f[i]=i;
          }
          for(int i=1;i<=n;i++)
          cin>>DIAN[i].x >>DIAN[i].y>>DIAN[i].h ;
          for(int i=1;i<=n;i++){
                  for(int j=1;j<=n;j++){
                          if(i==j)
                          continue;
                         w=1.0*sqrt((DIAN[i].x-DIAN[j].x)*(DIAN[i].x-DIAN[j].x)+(DIAN[i].y-DIAN[i].y)*(DIAN[i].y-DIAN[j].y))+(DIAN[i].h-DIAN[j].h)*(DIAN[i].h-DIAN[j].h);
                         xian[cnt++]={i,j,w};
                  }
          }
          sort(xian,xian+cnt,cmp);
          int sum1=0;
          double sum2=0.0;
          for(int i=0;i<cnt;i++){
          
                  if(find(xian[i].d1)!=find(xian[i].d2)){
                          root(xian[i].d1,xian[i].d2);
                          sum1++;
                          sum2+=xian[i].ju;
                          if(sum1==n-1)
                          break;
                  }
          }
          cout<<fixed<<setprecision(2)<<sum2;
          return 0;
}

FishC

这段代码中存在几个问题，导致无法正确计算最小生成树：

1. 缺少头文件引用：在代码开头缺少#include <iostream>，导致无法使用iostream库中的cout和cin函数。

2. 结构体定义问题：在结构体dian中，应在每个变量的后面加上分号";"。

3. 比较函数错误：在cmp函数的实现中，返回值错误。应该返回一个bool值，表示两个比较对象的大小关系，而不是double类型的值。

4. 输入错误：在for循环中输入DIAN.x、DIAN.y和DIAN.h的部分应该修改为cin >> DIAN.x >> DIAN.y >> DIAN.h；而不是>>DIAN.x >>DIAN.y>>DIAN.h。

以下是修改后的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
struct Dian{
        int x, y, h;
};
struct Xian{
        int d1, d2;
        double ju;
};

bool cmp(Xian x1, Xian x2){
        return x1.ju < x2.ju;
}

int find(int f, vector<int>& father){
        if (f == father[f])
                return f;
        else{
                father[f] = find(father[f], father);
                return father[f];
        }
}

void kruskal(vector<Xian>& xians){
        vector<int> father(n + 1);
        for (int i = 1; i <= n; i++){
                father[i] = i;
        }
        sort(xians.begin(), xians.end(), cmp);

        int cnt = 0;
        double w = 0;
        for (int i = 0; i < xians.size(); i++){
                int d1 = xians[i].d1;
                int d2 = xians[i].d2;
                double ju = xians[i].ju;

                int root1 = find(d1, father);
                int root2 = find(d2, father);

                if (root1 != root2){
                        cnt++;
                        w += ju;
                        father[root1] = root2;
                }

                if (cnt == n - 1)
                        break;
        }

        cout << "最小生成树的总权值为：" << w << endl;
}

int main(){
        cout << "请输入点的个数n：";
        cin >> n;

        vector<Dian> dian(n + 1);
        vector<Xian> xian(n * (n - 1) / 2);

        for (int i = 1; i <= n; i++){
                cout << "请输入第" << i << "个点的坐标（x, y）:";
                cin >> dian[i].x >> dian[i].y;
                cout << "请输入第" << i << "个点的高度h：";
                cin >> dian[i].h;
        }

        int k = 0;
        for (int i = 1; i <= n; i++){
                for (int j = i + 1; j <= n; j++){
                        xian[k].d1 = i;
                        xian[k].d2 = j;
                        xian[k].ju = sqrt(pow(dian[i].x - dian[j].x, 2) + pow(dian[i].y - dian[j].y, 2) + pow(dian[i].h - dian[j].h, 2));
                        k++;
                }
        }

        kruskal(xian);

        return 0;
}

希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。