pku1287.cpp

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

#include <stdio.h>
#include <stdlib.h>

typedef struct 
{
	int s, e, l;
} Way;

Way w[3000];
int un[55];
int P, N;

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

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

void kru()
{
	int i, j, sum;
	for (i = 1; i <= P; i++)
	{
		un[i] = i;
	}
	qsort(w, N, sizeof(w[0]), cp);

	for (i = 0, j = 1, sum = 0; i < N && j < P; i++)
	{
		if (get_id(w[i].s) == get_id(w[i].e))
		{
			continue;
		}
		un[get_id(w[i].e)] = get_id(w[i].s);
		j++;
		sum += w[i].l;
	}
	printf("%d\n", sum);
}

int main()
{
	int i;
	while (scanf("%d", &P) != -1 && P > 0)
	{
		scanf("%d", &N);
		for (i = 0; i < N; i++)
		{
			scanf("%d %d %d", &w[i].s, &w[i].e, &w[i].l);
		}
		kru();
	}
	return 0;
}