论坛 › C\C++交流 › 这个最小生成树哪一步不对

yueyufeng 发表于 2024-3-21 18:14:38

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

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

FishC 发表于 2024-3-21 18:14:53

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

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)
                return f;
        else{
                father = find(father, father);
                return father;
        }
}

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

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

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

                if (root1 != root2){
                        cnt++;
                        w += ju;
                        father = 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.x >> dian.y;
                cout << "请输入第" << i << "个点的高度h：";
                cin >> dian.h;
        }

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

        kruskal(xian);

        return 0;
}

希望对你有帮助！

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

查看完整版本: 这个最小生成树哪一步不对