- 一般无向图
- 建图
- 稠密图-prim算法
- 稀疏图-kruskal算法
![在这里插入图片描述](https://img-blog.csdnimg.cn/de179189addd4b0e9b72e768ae8e6ab1.png)
prim : 加点法
1.先随机选一个点,加入集合 ,之后寻找最短的距离的点加入集合,行程最小生成树。
2.注意最小生成树是不能有回路的, 所以可以把回路设置成最大值,即假装不存在。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int n;
int g[N][N], dist[N];
bool vis[N];
int res;
bool prim(){
memset(dist, 0x3f,sizeof dist);
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 1; j <= n; j++){
if(!vis[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
vis[t] = true;
if(i && dist[t] == 0x3f3f3f3f){
return false;
}
if(i) res+= dist[t];
for(int j = 1; j <= n; j++){
dist[j] = min(dist[j], g[t][j]);
}
}
return true;
}
int main(){
int m;
cin>>n>>m;
int u,v,w;
memset(g, 0x3f, sizeof g);
for(int i = 0; i < m; i++){
cin>>u>>v>>w;
if(u != v){
g[u][v] = g[v][u] = min(g[u][v],w);
}
}
bool ans = prim();
if(ans){
cout<<res<<'\n';
}else cout<<"impossible" << '\n';
return 0;
}