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

vizey

代码是残缺的，希望有大佬能帮帮我

城市间道路铺设问题
实现图的最小生成树问题的克鲁斯卡尔算法。

输入：
第一行两个整数，分别表示顶点个数n和边数m，从第二行到第m+1行，每行三个整数分别表示每条边的两个顶点号及权值。
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6

输出：
依次输出选中的n-1条边及最小生成树的权值之和
1 3 1
4 6 2
2 5 3
3 6 4
2 3 5
15

1. #include<bits\stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct edge{
   
5.         int u,v,weight;
   
6. }e[100];
   
7. 
   
8. void initialize(int n){
   
9.         for(int i=0;i<n;i++){
   
10.                
    
11.         }
    
12. }
    
13. 
    
14. int Find(int i){
    
15.        
    
16. }
    
17. 
    
18. void merge(int i,int j){
    
19.         if() return false;
    
20.         return true;
    
21. }
    
22. 
    
23. int Kruskal(int n, **e){
    
24.         int k,j,a,b;
    
25.         Sort(e, weight);  //将边按权重从小到大排序
    
26.         initialize(n);    //初始时每个顶点为一个集合
    
27.         k = j =1;            //k累计已选边的数目，j为所选的边在e中的序号
    
28.         while (k < n){      //选择n - 1条边
    
29.                 a = Find(e[j]);
    
30.                 b = Find(e[j]);  //找出第j条边两个端点所在的集合
    
31.                  if (a != b) {            //若不同，第j条边放入树中并合并这两个集合
    
32.                         t[k++] = j;
    
33.                         merge(a, b);
    
34.                 }  
    
35.                 j++;
    
36.         }
    
37. } //继续考察下一条边
    
38. 
    
39. int main(){
    
40.         int n,m;
    
41.         printf("请输入顶点个数n和边数m\n");
    
42.         scanf("%d%d",&n,&m);
    
43.         printf("\n请输入每条边对应的顶点号以及对应的权值\n");
    
44.         int i,j;
    
45.         for (i=0;i<m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].weight);
    
46. 
    
47.    
    
48.         return 0;
    
49. }

复制代码

最佳答案

月排行榜 / 总排行榜

grant1944

2021-9-7 21:18:23

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. }

复制代码

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

跳转到最佳答案楼层

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. }

复制代码

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