#include <iostream>
#include <string.h>

using namespace std;

struct node
{
	int x,y;
	int len;
}num[20005];

int cmp(const void *a,const void *b)
{
	
    struct node*c = (node *)a;
    struct node*d = (node *)b;
    return d->len - c->len;
}

int p[1008];

int Find_set(int x)
{
	if(x != p[x])
	{
		p[x] = Find_set(p[x]);
	}
	return p[x];
}

void Make_set(int x)
{
	int i;
	for(i=0; i<x; i++)
	{
		p[i] = i;
	}
}

int main()
{
	__int64 sum;
	int N,M;
	int i;
	cin>>N>>M;
	for(i=0; i<M; i++)
	{
		cin>>num[i].x>>num[i].y>>num[i].len;
	}
	qsort(num,M,sizeof(num[0]),cmp);
	Make_set(N);
	sum=0;
	for(i=0; i<M; i++)
	{	
		if(Find_set (p[num[i].x]) != Find_set (p[num[i].y]))
		{
		
			sum += num[i].len;
			p[Find_set(num[i].x)] = p[Find_set(num[i].y)];
		}
	}
	printf("%I64d", sum);
	return 0;
}

• Re:原来没判断连通性~~~~总算AC了~~~ (1195) jeepyutian 2009-04-10 14:45:17