首页 > 其他 > 详细

【模板】最小生成树

时间:2020-06-10 13:17:24      阅读:37      评论:0      收藏:0      [点我收藏+]

P3366 【模板】最小生成树

技术分享图片

 

 

//prim算法求最小生成树
#include <iostream> #include <cstring> using namespace std; const int N = 5010, INF = 0x3f3f3f3f; int n, m, d[N], g[N][N]; bool st[N]; int prime() { memset(d, 0x3f, sizeof d); int res = 0; for(int i = 0; i < n; i ++) { int t = -1; for(int j = 1; j <= n; j ++) if(!st[j] && (t == -1 || d[t] > d[j])) t = j; st[t] = true; if(i){ if(d[t] == INF) return INF; res += d[t]; } for(int j = 1; j <= n; j ++) if(d[j] > g[t][j]) d[j] = g[t][j]; } return res; } int main() { cin >> n >> m; memset(g, 0x3f, sizeof g); while(m --) { int a, b, c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c); } int t = prime(); if(t == INF) cout << "orz" << endl; else cout << t << endl; }

 

【模板】最小生成树

原文:https://www.cnblogs.com/longxue1991/p/13084419.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!