//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