pku2377.cpp

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

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

typedef struct 
{
	int cost;
	int s, e;
} Dis;

Dis d[21000];
int use[1001];

int getid(int id)
{
	int root;

	if (use[id] == -1)
	{
		return id;
	}
	else
	{
		root = getid(use[id]);
		use[id] = root;
		return root;
	}
}

int cmp(const void *a, const void *b)
{
	Dis *aa = (Dis *)a;
	Dis *bb = (Dis *)b;
	return bb->cost - aa->cost;	
}

int main()
{
	int l, i, j, n_house, n_path, cost, s, e;
	double total;
	char name1[21], name2[21];

	scanf("%d %d", &n_house, &n_path);
	
	for (j = 0; j < n_path; j++)
	{
		scanf("%d%d%d", &d[j].s, &d[j].e, &d[j].cost);
	}

	qsort(d, n_path, sizeof(d[0]), cmp);

	for (i = 0; i <= n_house; i++)
	{
		use[i] = -1;
	}

	for (i = 0, j = 0, cost = 0; i < n_house - 1 && j < n_path; j++)
	{
		if (getid(d[j].s) != getid(d[j].e))
		{
			use[getid(d[j].e)] = getid(d[j].s);
			i++;
			cost += d[j].cost;
		}
	}

	if (i < n_house - 1)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n", cost);
	}

	return 0;
}