[已解决]克鲁斯卡尔算法求助!

grant1944

1. #include <iostream>
   
2. #include <cstring>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. #define IOS \
   
6.     ios::sync_with_stdio(false); \
   
7.     cin.tie(0); \
   
8.     cout.tie(0)
   
9. const int N = 1e5+5,M = 2e5+5;
   
10. int n,m;
    
11. int p[N],path[N];
    
12. 
    
13. int find(int a){
    
14.     if (p[a] != a) p[a] = find(p[a]);
    
15.     return p[a];
    
16. }
    
17. 
    
18. struct Edge{
    
19.     int a,b,w;// 需要对边排序，用结构体存储
    
20.     bool operator< (const Edge& W) const{
    
21.         return w < W.w;// 重载小于号
    
22.     }
    
23. }edge[M];
    
24. 
    
25. int kruskal(){
    
26.     sort(edge + 1,edge + m + 1);// 数组从下标为1开始存边
    
27.     for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化并查集
    
28.    
    
29.     int res = 0,cnt = 0;// res存放最小生成树的边权之和，cnt存放最小生成树的边数
    
30.     for (int i = 1;i <= m;i ++){
    
31.         int a = edge[i].a,b = edge[i].b,w = edge[i].w;
    
32.         a = find(a),b = find(b);
    
33.         if (a != b){
    
34.             p[a] = b;
    
35.             res += w;
    
36.             cnt ++;
    
37.             path[cnt] = i;
    
38.         }// n个点一共n-1条边
    
39.         if (cnt == n-1) break;// 处理完提前退出
    
40.     }
    
41.     return res;
    
42. }
    
43. 
    
44. int main(){
    
45.     IOS;
    
46.    
    
47.     cin >> n >> m;
    
48.     int u,v,w;
    
49.     for (int i = 1; i <= m; i ++ ){
    
50.         cin >> u >> v >> w;
    
51.         edge[i] = {u,v,w};
    
52.     }
    
53.    
    
54.     int res = kruskal();
    
55. 
    
56.     for (int i = 1;i <= n-1;i ++){
    
57.         int id = path[i];
    
58.         cout << edge[id].a << ' ' << edge[id].b << ' ' << edge[id].w << '\n';
    
59.     }
    
60.     cout << res << '\n';
    
61.     return 0;
    
62. }

复制代码

自己写的，没有按照你给的代码