Posted on 2009-08-28 09:17
reiks 阅读(274)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct Edge
{
int x, y, w; /**//*边集，边(x,y)，权为c*/
}e[20001];
int rank[1001]; /**//*节点的秩*/
int p[1001]; /**//*p[x]表示x节点父节点*/
int ans=0;
int ma;
void Make(int x)
{
p[x] = x;
rank[x] = 1;
}
int Find(int x) /**//*查找x所在集合子树的根*/
{
if (x == p[x]) return x;
return p[x] = Find( p[x] );;
}
void Union(int x, int y, int c)
{
x = Find(x);
y = Find(y);
if ( x != y ) /**//*若x,y不属于同一集合*/
{
if ( rank[x] > rank[y] ) /**//*将秩较小的树连接到秩较大的树后*/
{
p[y] = x;
}
else
{
if(rank[x] == rank[y])
rank[y]++;
p[x] = y;
}
ans += c;
ma++;
}
}
bool cmp (const Edge & a, const Edge & b)
{
return a.w > b.w;
}
int N, M;
int main()
{
int n; /**//*边的条数*/
int i;
//ifstream in("123.txt");
ans=0;
ma = 1;
scanf("%d %d", &N, &M);
//cin >> N >> M;
for ( i = 1; i <= N; ++i)
Make(i);
for ( i = 0; i < M; ++i)
{
scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
}
sort(e, e + M, cmp); /**//*按权值非降序排序*/
for ( i = 0; i < M; ++i)
{
Union(e[i].x, e[i].y, e[i].w);
}
if (ma == N)
printf("%d", ans);
else
printf("-1");
//system("pause");
return 0;
}