题目分析
来源：acwing
分析：
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
朴素prim算法思路：
距离初始化为∞迭代n次（集合S表示：当前连通块中的所有点）
每次找到集合外距离集合最近的点 t
用t更新其他点到集合的距离
将t加入集合
可以发现，思路和dijkstra算法很像，dijkstra算法是用t更新其他点到起点的距离，而prim算法是用t更新其他点到集合的距离。
最小生成树：图中可能存在重边和自环，边权可能为负数。
ac代码
#include<bits/stdc++.h>using namespace std;const int N = 510;const int INF = 0x3f3f3f3f;int n, m;int g[N][N];int dist[N];bool st[N];int prim(){memset(dist, 0x3f, sizeof dist);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 || dist[t] > dist[j]))t= j;// 不连通的if(i && dist[t] == INF) return INF;if(i) res += dist[t];// 注意这里和dijkstra的区别// prim的距离是：该点和集合中某点的距离，直接就是g[t][j];for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);st[t] = true;}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 = prim();if( t == INF) puts("impossible");else cout << t << endl;}
题目来源
/problem/content/860/
