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