#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define maxn 500006
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int fa[maxn],n,m,cnt=0,tot=0;
ll ans=0;
struct edge{int u,v,w;}e[maxn<<1];
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
inline bool cmp(edge a,edge b){return a.w<b.w;}
int main()
{
n=read(),m=read();
rep(i,1,m){
int x=read(),y=read(),z=read();
e[++cnt]=(edge){x,y,z};e[++cnt]=(edge){y,x,z};
}
rep(i,1,n)fa[i]=i;
sort(e+1,e+1+cnt,cmp);
rep(i,1,cnt){
int r1=find(e[i].u),r2=find(e[i].v);
if(r1!=r2){
if(i&1)fa[r1]=r2;
else fa[r2]=r1;
ans+=e[i].w;tot++;
}
if(tot==n-1)break;
}
printf(LL,ans);
}
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr
