AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
芳_8
,
2023-11-18 18:52:05
,
所有人可见
,
阅读 40
算法
(Prim)
时间复杂度 $O(n^2)$
参考文献
yxc的视频
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505,M=0x3f3f3f3f;//M定成大数,以防重复
int n,m;
int g[N][N];//G:邻接矩阵
int d[N];
bool st[N];
int prim(){
memset(d, 0x3f, sizeof d);//定义成63
int cnt = 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;
}
if (i && d[t] == M) return M;//不合格,淘汰
if (i) cnt += d[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) d[j] = min(d[j], g[t][j]);
}
return cnt;//“合格品”返回
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= m; i ++ ){
int a, b, c;//输入
cin >> a >> b >> c ;
g[a][b] = g[b][a] = min(g[a][b], c);//存在邻接矩阵里
}
int t = prim();//“t”存放结果
if (t == M) cout << "impossible";//不合格输出
else cout << t;//合格输出
}