AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
YSW_7
,
2023-01-11 16:38:44
,
所有人可见
,
阅读 152
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
#define pii pair<int,int>
/*******************初始化*/
int n,m;
const int N=510,INF=0x3f3f3f3f;
int p[N][N];
int st[N];
int d[N];
/*******************函数*/
int prim(){
memset(d,0x3f,sizeof d);
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||d[t]>d[j])){
t=j;
}
}
if(i&&d[t]==INF) return INF;//如果不是第一个插入的点 并且我们选出的最小点距离集合的距离是INF
//说明这个图存在不连通 那就无法生成树
if(i) res+=d[t];//如果不是第一个插入的点 并且这个点是联通的 那么我们就将这个点距离集合的距离加上
//加入权值与更新其他距离顺序不能颠倒 因为图中如果有个点存在自环且自环的边权是负值
//那么没更新一次 这个点就会将自己距离集合的距离减小一次 但是树中是不允许出现环的
for(int j=1;j<=n;j++){//在用这个点来更新 这个点的出边老更新出变点距离集合的距离;
d[j]=min(d[j],p[t][j]);
}
st[t]=1;
}
return res;
}
/*******************主函数*/
signed main(){
cin>>n>>m;
memset(p,0x3f,sizeof p);
while(m--){
int a,b,c;
cin>>a>>b>>c;
p[a][b]=p[b][a]=min(p[a][b],c);
}
int t=prim();
if(t==INF) cout<<"impossible"<<endl;
else cout<<t<<endl;
}