最小生成树-prim算法模板
2023-03-14 10:16:29 时间
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define inf 10000000 #define maxn 21 int m,n; int edge[maxn][maxn],lowcost[maxn],nearvex[maxn]; void prim(int u0) { int i,j; int sumweight=0; for(i=1; i<=n; i++) { lowcost[i]=edge[u0][i]; nearvex[i]=u0; } nearvex[u0]=-1; for(i=1; i<n; i++) { int min=inf; int v=-1; for(j=1; j<=n; j++) { if(nearvex[j]!=-1 && lowcost[j]<min) { v=j; min=lowcost[j]; } } if(v!=-1) { cout<<nearvex[v]<<" "<<v<<" "<<lowcost[v]<<endl; nearvex[v]=-1; sumweight+=lowcost[v]; for(j=1; j<=n; j++) { if(nearvex[j]!=-1 && edge[v][j]<lowcost[j]) { lowcost[j]=edge[v][j]; nearvex[j]=v; } } } } cout<<"weight of mst is "<<sumweight<<endl; } int main() { ios::sync_with_stdio(false); freopen("1.txt","r",stdin); int i,j,w,u,v; cin>>n>>m; memset(edge,0,sizeof(edge)); for(i=1; i<=m; i++) { cin>>u>>v>>w; edge[u][v]=edge[v][u]=w; } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(i==j) edge[i][j]=0; else if(edge[i][j]==0) edge[i][j]=inf; } } prim(1); return 0; } /* 7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24 */
相关文章
- 50 万行 Go 代码,美国一组织从 Python 2 迁移到 Go
- 从代码层读懂Java HashMap的实现原理
- 谷歌的最新NLP模型,现在能陪你从诗词歌赋谈到人生哲学
- 不要再天天写表单了,淘宝大牛教你零基础写PHP扩展
- Java Web模板代码生成器的设计与实现
- 我们一起学习RSA-PSS 算法
- 关于Git的几个使用技巧
- SpaceX 使用 Rust 为部分新项目构建原型
- signalR+redis分布式聊天服务器搭建
- Git如何处理大仓库
- 想要写出好味道的代码,你需要养成这些好习惯!
- 用C语言写面向的对象是一种什么样的体验
- 历时大半年,Github团队成功减少30kb依赖体积
- 聊聊Clean Code的编码、重构技巧
- 调查:企业越来越依赖开源软件
- 产品经理:你能不能用Div给我画条龙?
- 中级程序员还应该如何提高自己?
- 七招掌控软件的代码质量
- PHP垃圾回收机制详解
- React Hooks 在 SSR 模式下常见问题及解决方案