新手从零基础建站初级网站建设,html5软件下载电脑版,丰台seo网站关键词优化,江苏连云港网站建设公司7-92 最小生成树-kruskal 分数 10
全屏浏览题目 作者 任唯 单位 河北农业大学 题目给出一个无向连通图#xff0c;要求求出其最小生成树的权值。
温馨提示#xff1a;本题请使用kruskal最小生成树算法。
输入格式: 输出格式: 输出一个整数表示最小生成树的各边的长度之和。…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
#includebits/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.valueb.value;
}//以边从小到大排序
int main(){int n,m;cinnm;for(int i1;im;i){scanf(%d%d%d, s[i].u, s[i].v, s[i].value);//这里要用scanf如果用cin会报运行超时}//数据的输入int num0,sum0;sort(s1,sm1,cmp);//对边进行排序for(int i1;in;i){f[i]i;}for(int i0;im;i){int fufind(s[i].u);int fvfind(s[i].v);if(fu!fv){f[fu]fv;sums[i].value;num;if(numn-1)//边数为顶点数-1所有最小边都已经找到就可以退出了break;}}coutsum;return 0;
}
