查看原题
题意
最小生成树
思路
Prim 我套了之前的模板
代码
#include <iostream>
using namespace std;
int main(
int argc,
char *argv[])
{
int n,a,b,x;
while(
cin>>n&&n){
int num[
101][
101],visted[
101]={
0},lowest[
101]={
999999};
for(
int i=
0;i<=n;i++){
for(
int j=
0;j<=n;j++){
num[i][j]=
999999;
}
}
for(
int i=
0;i<n*(n-
1)/
2;i++){
cin>>a>>b>>x;
if(x<num[a][b]){
num[a][b]=num[b][a]=x;
}
}
int step=
1,temp,sum=
0,i,j;
for(i=
1;i<=n;i++){
lowest[i]=num[step][i];
}
visted[step]=
1;
for(i=
1;i<n;i++){
temp=
999999;
for(j=
1;j<=n;j++){
if(!visted[j]&&lowest[j]<temp){
temp=lowest[j];
step=j;
}
}
visted[step]=
1;
sum+=temp;
for(
int k=
1;k<=n;k++){
if(!visted[k]&&num[step][k]<lowest[k]){
lowest[k]=num[step][k];
}
}
}
cout<<sum<<endl;
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-500217.html