本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。
代码语言：javascript复制#include<iostream>
using namespace std;
#define MAX 100
#define MAXCOST 10000
int prim(int arr[MAX][MAX],int n){
int lowcost[MAX];
int mst[MAX];
int cost=0;
for(int i=0;i<n;i ){
lowcost[i]=arr[0][i];
mst[i]=n;
cout<<"lowcost[i]"<<lowcost[i]<<endl;
}
mst[0]=-1;
cout<<"0";
for(int i=1;i<n;i ){
int min=MAXCOST,minid=0;
for(int j=0;j<n;j ){
if(lowcost[j]<min&&mst[j]!=-1){
min=lowcost[j];
minid=j;
}
}
cout<<"->"<<minid;
cost =lowcost[minid];
//cout<<"lowcost[minid]"<<lowcost[minid]<<"cost"<<cost<<endl;
//lowcost[minid]=0;
mst[minid]=-1;
for(int j=0;j<n;j ){
if(mst[j]!=-1&&arr[minid][j]<lowcost[j]){
lowcost[j]=arr[minid][j];
mst[j]=minid;
}
}
}
return cost;
}
int main(){
int n,m,x,y,cost,arr[MAX][MAX];
for(int i=0;i<MAX;i ){
for(int j=0;j<MAX;j ){
if(i==j){
arr[i][j]=0;
}else{
arr[i][j]=MAXCOST;
}
}
}
cin>>n>>m;
for(int i=0;i<m;i ){
cin>>x>>y>>cost;
//x--;
//y--;
arr[x][y]=cost;
arr[y][x]=cost;
}
cout<<endl<<"prim"<<prim(arr,n);
return 0;
} Post Views: 313
