AcWing 3270. 数据中心csp15(4)
原题链接
简单
作者:
YAX_AC
,
2024-11-25 18:00:21
,
所有人可见
,
阅读 2
//求一个最大边权最小的生成树
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50010,M = 100010;
int n,m;
struct Edge
{
int a,b,c;
bool operator< (const Edge&t) const
{
return c<t.c;
}
}edge[M];
int p[N];
int find(int x)
{
if(p[x]!=x) return p[x] = find(p[x]);
return p[x];
}
int main()
{
//%*d过滤一个整数,%*s过滤一个字符串
scanf("%d%d%*d",&n,&m);
for(int i = 1; i<=n; i++) p[i] = i;
for(int i = 0; i<m; i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[i] = {a,b,c};
}
sort(edge,edge+m);
int res = 0;
for(int i = 0; i<m; i++)
{
int a = edge[i].a, b = edge[i].b, c = edge[i].c;
if(find(a)!=find(b))
{
p[find(a)] = find(b);
res = c;//更新边权Tmax=max(Th)
//因为c是从小到大枚举的,最后一个更新c,是最大权值,即为答案
}
}
cout<<res;
return 0;
}