#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 2e5+; struct node{
LL u,v,w;
node(){}
node(LL a,LL b,LL c):u(a),v(b),w(c){}
}; LL f[maxn];
LL n,m;
vector<node>edge;
int Find(LL x)
{
if (f[x] != x)
f[x] = Find(f[x]);
return f[x];
} void Union(LL a, LL b)
{
int a1 = Find(a);
int b1 = Find(b);
if (a1 != b1)
f[a1] = b1;
}
bool cmp1(node a,node b)
{
return a.w>b.w;
}
bool cmp2(node a,node b)
{
return a.w<b.w;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;i++)
f[i]=i;
for(int i=;i<m;i++){
LL a,b,c;
cin>>a>>b>>c;
edge.push_back(node(a,b,c));
}
sort(edge.begin(),edge.end(),cmp2);
LL k=,max_num=-;
for(int i=;i<m;i++)
{
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
max_num = max(max_num,edge[i].w);
k++;
}
if(k==(n-))
break;
}
sort(edge.begin(),edge.end(),cmp1);
for(int i=;i<=m;i++)
f[i]=i;
LL ans=;
k=;
for(int i=;i<m;i++)
{
if(edge[i].w>max_num)continue;
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
ans += edge[i].w;
k++;
}
if(k==(n-))
break;
}
cout<<ans<<endl;
return ;
}
05-28 07:34
查看更多