pku2075.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 1000

double d[SIZE][SIZE], mindis[SIZE];
int use[SIZE];
char name[SIZE][21];

int getid(int id)
{
	int root;

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

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

	scanf("%lf", &total);
	scanf("%d", &n_house);

	for (i = 0; i < n_house; i++)
	{
		d[i][j] = 0;
		for (j = i + 1; j < n_house; j++)
		{
			d[i][j] = d[j][i] = 1e30;
		}
	}
	
	for (i = 0; i < n_house; i++)
	{
		scanf("%s", name[i]);
	}
	
	scanf("%d", &n_path);
	for (j = 0; j < n_path; j++)
	{
		scanf("%s%s%lf", name1, name2, &dis);

		for (i = 0; i < n_house; i++)
		{
			if (strcmp(name1, name[i]) == 0)
			{
				s = i;
				break;
			}
		}
		for (i = 0; i < n_house; i++)
		{
			if (strcmp(name2, name[i]) == 0)
			{
				e = i;
				break;
			}
		}
		if (d[s][e] > dis)
		{
			d[s][e] = d[e][s] = dis;
		}
	}

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

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

	for (i = 1, dis = 0; i < n_house; i++)
	{
		min = 1e30;
		for (j = 1; j < n_house; j++)
		{
			if (use[j] == 0 && min > mindis[j])
			{
				min = mindis[j];
				u = j;
			}
		}
		use[u] = 1;
		dis += mindis[u];

		for (j = 0; j < n_house; j++)
		{
			if (use[j] == 0 && mindis[j] > d[u][j])
			{
				mindis[j] = d[u][j];
			}
		}
	}

	if (dis <= total)
	{
		printf("Need %.1lf miles of cable\n", dis);
	}
	else
	{
		printf("Not enough cable\n");
	}
	return 0;
}