分析:MST,用最好理解的克鲁斯卡尔算法,其中 fin 是寻找这个点的父节点并进行路径压缩,merge 是把这两个点合并在一起,表示现在已经是相连接的了,克鲁斯卡尔算法要求需要先对边权来排序,所以首先用个结构体来存 起点 - 终点 - 权值,然后按权值从大到小排序,依次选取最小边权。
代码语言:javascript复制#include <iostream>
#include <bits/stdc .h>
using namespace std;
struct node
{
int b,e;
int w;
}s[3005];
bool cmp(struct node a, struct node b)
{
return a.w < b.w;
}
bool vis[1005];
int c[10005];
int fin(int x)
{
int r = x;
while(r != c[r]){
r = c[r];
}
int i = x, j;
while(c[i] != r)
{
j = c[i];
c[i] = r;
i = j;
}
return r;
}
int merge(int x, int y)
{
if(fin(x) != fin(y))
{
c[fin(x)] = fin(y);
return 1;
}
return 0;
}
int main()
{
int n,m,ans = 0,cnt = 0;
while(~scanf("%d%d",&n,&m)){
for(int i = 0; i < m; i )
{
scanf("%d%d%d",&s[i].b,&s[i].e,&s[i].w);
}
for(int i = 0; i <= n; i )c[i] = i;
sort(s,s m,cmp);
ans = 0;
cnt = 0;
for(int i = 0; i < m; i )
{
if(merge(s[i].b,s[i].e) == 1)
{
ans = s[i].w;
cnt ;
}
if(cnt == n - 1) break;
}
if(cnt == n - 1)
{
printf("%dn",ans);
}
else printf("-1n");
}
return 0;
}