题目链接

/problem/content/description/860/

思路

prim算法的思想就是，我们维护一个最优集合，然后寻找所有不在集合的点连向集合的最短边，然后将这个点加入集合，并将权值加入总权值中，对于每一个最短边的点，我们用该点更新一下其他点到集合的距离就好了（这里和迪杰斯特拉不太一样，迪杰斯特拉是更新下一个点到源点的距离，而这里是更新没在集合中的点到集合的距离）

代码

#include<bits/stdc++.h>using namespace std;const int N = 500+10;int n,m;int g[N][N];int dis[N];int vis[N];const int INF = 0x3f3f3f3f;int prim(){memset(dis,0x3f,sizeof dis);int ans = 0;for(int i = 0;i < n; ++i){int t = -1;for(int j = 1;j <= n; ++j){if(!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;}if(i && dis[t] == INF) return INF;//如果不是第一个点并且下一个点的位置为正无穷，说明不联通if(i) ans += dis[t];//如果不是第一个点，那么就说明有一条边连向我们的最小生成树集合中vis[t] = true;//将当前的t更新为访问for(int j = 1;j <= n; ++j) if(!vis[j]) dis[j] = min(dis[j],g[t][j]);//如果不在集合中，那么就选择是否更新}return ans;}int main(){scanf("%d%d",&n,&m);memset(g,0x3f,sizeof g);for(int i = 0;i < m; ++i) {int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u][v] = min(g[u][v],w);g[v][u] = g[u][v];}int ans = prim();if(ans == INF) printf("impossible");else printf("%d\n",ans);return 0;}