题目描述
prim算法求最小生成树,本算法选择跟dijkstra算法一样,加入一个初始点。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int N=510;
int g[N][N];
bool tg[N];
int d[N];
void prim(){
memset(d,0x3f,sizeof d);
d[1]=0;
for(int i=0;i<n;i++){
int x=-1;
for(int j=1;j<=n;j++)
if(!tg[j]&&(x==-1||d[x]>d[j]))x=j;
tg[x]=true;
if(d[x]==0x3f3f3f3f){cout<<"impossible";return;}
for(int j=1;j<=n;j++)
if(!tg[j]&&d[j]>g[x][j])d[j]=g[x][j];
}
int res=0;
for(int j=1;j<=n;j++)res+=d[j];
cout<<res;
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
cin>>a>>b>>c;
if(a!=b){g[a][b]=min(g[a][b],c);g[b][a]= min(g[b][a],c);}
}
prim();
return 0;
}