题目：

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。

Input

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

Output

输出最小生成树的所有边的权值之和。

Sample Input

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

Sample Output

37

思路分析：点少边多用kruskal算法。将每条边的属性存入数组，然后根据权值从小到达排序。用并查集思想依次将点关连起来，直到有n-1条边形成。这n-1条边的权值之和就是最小生成树了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+7;

struct node{
	int a, b, c;
};
struct node road[50000+7];

int pre[MAXN];
void init()
{
	for( int i=0; i<MAXN; i++ )
		pre[i] = i;
}
int find( int x )
{
	if( pre[x] != x )
		return pre[x] = find(pre[x]);
	return pre[x];
}

bool cmp( node r1, node r2 )
{
	return r1.c < r2.c;
}
int main()
{
	int n, m;
	while( ~scanf("%d%d", &n, &m) )
	{
		for( int i=0; i<m; i++ )
			scanf("%d%d%d", &road[i].a, &road[i].b, &road[i].c);
		sort(road, road+m, cmp);
		init();
		int cnt = 0;
		int cost = 0;
		for( int i=0; i<m; i++ )
		{
			int tmp1 = find(road[i].a);
			int tmp2 = find(road[i].b);
			if( tmp1 != tmp2 )
			{
				pre[tmp1] = tmp2;
				cost += road[i].c;
				cnt ++;
				if( cnt == n-1 )
					break;
			}
		}
		printf("%d\n", cost);

	}

	return 0;
}