席一鸣 2014-10-04 01:48:43
点我顶贴
收藏
删除
#include<algorithm>
#include<iostream>
using namespace std;
struct q
{
int a,b,c;
}p[100001];
int f[100001];
int c(q a,q b)
{
return a.c<b.c;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
main()
{
int m,n,i,x,y,k=0;
long long s=0,t=0;
cin>>n>>m;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
{
cin>>p[i].a>>p[i].b>>p[i].c;
t+=p[i].c;
}
sort(p+1,p+m+1,c);
for(i=1;i<=m;i++)
{
x=find(p[i].a);
y=find(p[i].b);
if(x!=y)
{
f[x]=y;
s+=p[i].c;
k++;
if(k==n-1)
break;
}
}
cout<<t-s;
}