PTA 最小生成树-kruskal

2023-12-25 13:27:35

7-92 最小生成树-kruskal
分数 10

全屏浏览题目
作者 任唯
单位 河北农业大学
题目给出一个无向连通图,要求求出其最小生成树的权值。

温馨提示:本题请使用kruskal最小生成树算法。

输入格式:


?

输出格式:


输出一个整数表示最小生成树的各边的长度之和。

输入样例:
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例:
7
代码长度限制
16 KB
时间限制
500 ms
内存限制
64 MB

代码分享及思路分享:


#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
struct edge{
    int u,v;
    int value;
}s[1000001];
int f[1000001];//用f数组的下标和对应存储的值来判断是否已经连通
int find(int x){
    if(x!=f[x])  return f[x]=find(f[x]);
    return f[x];
}//调用递归
bool cmp(edge a,edge b){
    return a.value<b.value;
}//以边从小到大排序
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
     scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].value);//这里要用scanf如果用cin会报运行超时
    }//数据的输入
    int num=0,sum=0;
    sort(s+1,s+m+1,cmp);//对边进行排序
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=0;i<=m;i++){
        int fu=find(s[i].u);
        int fv=find(s[i].v);
        if(fu!=fv){
            f[fu]=fv;
            sum+=s[i].value;
            num++;
            if(num==n-1)//边数为顶点数-1,所有最小边都已经找到就可以退出了
                break;
        }
    }
    cout<<sum;
    return 0;
}

文章来源:https://blog.csdn.net/qq_73062949/article/details/135197086
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。