朴素版的Prim算法
适合稠密图 ，稠密图适合用邻接矩阵存储
核心操作
1、 dist[i] 初始化为正无穷
2、集合s 表示在当前连通块内的所有点
3、for(i=1~n)
找到在集合外的距离最近的点->t
4、用t来更新其他点到集合的距离
5、把他加入到集合当中去 st[t]=true;
（边的正负都可以）
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dis[N];//表示集合外的点到集合的距离
bool vis[N];
int Prim() {
memset(dis, 0x3f, sizeof(dis));//到集合的距离初始为无穷
int res = 0;
for (int i = 1; i <= n; i++) {
int t = -1; //判断是否为初始点
for (int j = 1; j <= n; j++) {
if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
t = j;//如果是初始点则加入到集合 或者如果到集合的距离最小则加入到集合
}
}
if (i > 1 && dis[t] == INF)return INF;//如果不是初始点 且 到集合的最小距离是无穷 则返回impossible
if (i > 1) res += dis[t]; //如果不是初始点 则累加最小生成树边权
vis[t] = true;//将点加入到集合中
for (int j = 1; j <= n; j++) {//用新加入的点更新距离
dis[j] = min(dis[j], g[t][j]);//g[t][j] 表示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] = min(g[a][b], c); //由于是无向图 所有 g[a][b]和g[b][a]都初始化
g[b][a] = min(g[a][b], c);
}
int t = Prim();
if (t == INF)
cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
