pku2395.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct 
{
	int s, e, l;
} Edge;

Edge e[10001];
int nd[2002];
int N, E;

int cp(const void *a, const void *b)
{
	Edge *aa = (Edge*)a;
	Edge *bb = (Edge*)b;
	return aa->l - bb->l;
}

int get_id(int x)
{
	if (nd[x] == 0)
	{
		return x;
	}
	return nd[x] = get_id(nd[x]);
}

int main()
{
	int i, j, hs, he;
	while (scanf("%d%d", &N, &E) != -1)
	{
		for (i = 0; i < E; i++)
		{
			scanf("%d %d %d", &e[i].s, &e[i].e, &e[i].l);
		}
		qsort(e, E, sizeof(e[0]), cp);
		memset(nd, 0, sizeof(nd));
		for (i = 0, j = 1; i < E && j < N; i++)
		{
			hs = get_id(e[i].s);
			he = get_id(e[i].e);
			if (hs != he)
			{
				nd[he] = hs;
				j++;
			}
		}
		printf("%d\n", e[i - 1].l);
	}
	return 0;
}