Posted on 2009-08-28 09:17
reiks 閱讀(293)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結(jié)構(gòu)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct Edge
{
int x, y, w; /**//*邊集，邊(x,y)，權(quán)為c*/
}e[20001];
int rank[1001]; /**//*節(jié)點的秩*/
int p[1001]; /**//*p[x]表示x節(jié)點父節(jié)點*/
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; /**//*邊的條數(shù)*/
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); /**//*按權(quán)值非降序排序*/
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;
}