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

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。

以下是修改后的代码：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int n;
   
7. struct Dian{
   
8.         int x, y, h;
   
9. };
   
10. struct Xian{
    
11.         int d1, d2;
    
12.         double ju;
    
13. };
    
14. 
    
15. bool cmp(Xian x1, Xian x2){
    
16.         return x1.ju < x2.ju;
    
17. }
    
18. 
    
19. int find(int f, vector<int>& father){
    
20.         if (f == father[f])
    
21.                 return f;
    
22.         else{
    
23.                 father[f] = find(father[f], father);
    
24.                 return father[f];
    
25.         }
    
26. }
    
27. 
    
28. void kruskal(vector<Xian>& xians){
    
29.         vector<int> father(n + 1);
    
30.         for (int i = 1; i <= n; i++){
    
31.                 father[i] = i;
    
32.         }
    
33.         sort(xians.begin(), xians.end(), cmp);
    
34. 
    
35.         int cnt = 0;
    
36.         double w = 0;
    
37.         for (int i = 0; i < xians.size(); i++){
    
38.                 int d1 = xians[i].d1;
    
39.                 int d2 = xians[i].d2;
    
40.                 double ju = xians[i].ju;
    
41. 
    
42.                 int root1 = find(d1, father);
    
43.                 int root2 = find(d2, father);
    
44. 
    
45.                 if (root1 != root2){
    
46.                         cnt++;
    
47.                         w += ju;
    
48.                         father[root1] = root2;
    
49.                 }
    
50. 
    
51.                 if (cnt == n - 1)
    
52.                         break;
    
53.         }
    
54. 
    
55.         cout << "最小生成树的总权值为：" << w << endl;
    
56. }
    
57. 
    
58. int main(){
    
59.         cout << "请输入点的个数n：";
    
60.         cin >> n;
    
61. 
    
62.         vector<Dian> dian(n + 1);
    
63.         vector<Xian> xian(n * (n - 1) / 2);
    
64. 
    
65.         for (int i = 1; i <= n; i++){
    
66.                 cout << "请输入第" << i << "个点的坐标（x, y）:";
    
67.                 cin >> dian[i].x >> dian[i].y;
    
68.                 cout << "请输入第" << i << "个点的高度h：";
    
69.                 cin >> dian[i].h;
    
70.         }
    
71. 
    
72.         int k = 0;
    
73.         for (int i = 1; i <= n; i++){
    
74.                 for (int j = i + 1; j <= n; j++){
    
75.                         xian[k].d1 = i;
    
76.                         xian[k].d2 = j;
    
77.                         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));
    
78.                         k++;
    
79.                 }
    
80.         }
    
81. 
    
82.         kruskal(xian);
    
83. 
    
84.         return 0;
    
85. }

复制代码

希望对你有帮助！

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