解题思路:
留个笔记,普鲁斯卡尔算法(和本题数据不符)
注意事项:
参考代码:
#include <iostream> using namespace std; struct mp{ int x; int y; int s; }e[105]; int note[105]; bool check(int a,int b); int root(int x); bool cmp(mp a,mp b); int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ cin>>e[i].x>>e[i].y>>e[i].s; //输入数据 } for(int i=1;i<=n;i++) //初始化 note[i]=i; sort(e,e+m,cmp); int sum=0,count=0;//排序 for(int i=0;i<m;i++){ //m条边 if(check(e[i].x,e[i].y)){ //并查集判断是否连通 sum+=e[i].s; //没有连通,权值加起来 count++; //记录数量 cout<<e[i].s<<endl; } if(count==n-1) //count为n-1说明 最小生成树已经构建 break; } cout<<sum<<endl; return 0; } bool cmp(mp a,mp b){ return a.s<b.s; } bool check(int a,int b){ int fx=root(a); int fy=root(b); if(fx!=fy){ note[fx]=fy; return 1; } return 0; } int root(int x){ int r=x; while(note[r]!=r){ r=note[r]; } int j,i=x; while(i!=r){ j=note[i]; note[i]=r; i=j; } return r; }
0.0分
0 人评分
C语言考试练习题_保留字母 (C语言代码)浏览:694 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:698 |
C二级辅导-同因查找 (C语言代码)浏览:585 |
简单的a+b (C++语言代码)浏览:860 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1059 |
WU-陶陶摘苹果2 (C++代码)浏览:975 |
WU-整除问题 (C++代码)浏览:612 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1358 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:702 |
1011题解浏览:765 |