#include<iostream>
#include<algorithm>
using namespace std;
const int N(1000);
struct edge
{
int from,to,wei;
bool operator <(const edge &x)const
{
return wei<x.wei;
}
};
int n,en,a[N];
edge e[10000];
void init()
{
cin>>n>>en;
for (int i=0;i<en;i++) cin>>e[i].from>>e[i].to>>e[i].wei;
}
int f(int x)
{
while (a[x]!=x) x=a[x];
return x;
}
//bool comp(const edge &x,const edge &y)
//{
// return x.wei<y.wei;
//}
int mst()
{
int i,k1,k2,ans=0,added=0;
for (i=1;i<=n;i++) a[i]=i;
for (i=0;i<en;i++)
{
k1=f(e[i].from);
k2=f(e[i].to);
if (k1!=k2)
{
ans+=e[i].wei;
if (++added==n-1) break;
a[k2]=k1;
a[e[i].from]=k1;
a[e[i].to]=k1;
}
}
return ans;
}
int main()
{
init();
sort(e,e+en);
cout<<mst()<<endl;
system("pause");
return 0;
}
posted on 2011-10-30 10:35
龙在江湖 阅读(369)
评论(0) 编辑 收藏 引用 所属分类:
图论