#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 5000;
int WG[MAXN][MAXN];
bool ft[MAXN];
int n = 0;
int e = 0;
int table[MAXN][2]; //记录表
void add(int x,int y,int c){
WG[x-1][y-1] = WG[y-1][x-1] = c;
}
void CG(int e){
for(int i=0;i<e;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
}
int Prim(int vs){ //生成最小生成树
int min_n = 0x3f3f3f3f;
for(int i=1;i < n;i++){
ft[vs] = 1;
min_n = 0x3f3f3f3f;
int min_i = -1;
for(int j=0;j < n;j++){ //更新表并找出最小值
if((ft[j]==0)&&(WG[vs][j]<=table[j][0])){
table[j][0] = WG[vs][j];
table[j][1] = vs;
}
if((ft[j]==0)&&(min_n>=WG[vs][j])){
min_n = WG[vs][j];
min_i = j;
}
}
vs = min_i; //将最小值作为下一个起点
}
int max_n = -1;
for(int i=1;i < n;i++) max_n = max(max_n,table[i][0]);
return max_n; //返回最长路径
}
int main(){
int final_max = -1;
memset(WG,0x3f,sizeof(WG));
memset(ft,0,sizeof(ft));
memset(table,0x3f,sizeof(table));
cin>>n>>e;
CG(e);
int temp = Prim(0);
if(temp!=0x3f3f3f3f)
final_max = temp;
cout<<final_max;
return 0;
}
全部评论
(0) 回帖