pku2031.cpp

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

#include <stdio.h>
#include <math.h>
#define TheMax 1e30
typedef struct 
{
	double x, y, z, r;
} Point;

Point p[101];
int N;
double mindis[101], sum;

double Dis(int i, int j)
{
	double ans;
	ans = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y) + (p[i].z - p[j].z) * (p[i].z - p[j].z));
	ans -= p[i].r + p[j].r;
	if (ans > 0)
	{
		return ans;
	}
	return 0;
}

double Prim()
{
	int i, j, u;
	double min, tmp;
	int st[101];
	st[0] = 1;
	for (i = 1; i < N; i++)
	{
		mindis[i] = Dis(i, 0);
		st[i] = 0;
	}
	for (j = 1, sum = 0; j < N; j++)
	{
		min = TheMax;
		u = -1;
		for (i = 1; i < N; i++)
		{
			if (!st[i] && mindis[i] < min)
			{
				min = mindis[i];
				u = i;
			}
		}
		st[u] = 1;
		sum += min;
		for (i = 1; i < N; i++)
		{
			if (!st[i])
			{
				tmp = Dis(u, i);
				mindis[i] = (mindis[i] < tmp) ? mindis[i] : tmp;
			}
		}
	}
	return sum;
}

int main()
{
	int i;
	while (scanf("%d", &N) != -1 && N > 0)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%lf %lf %lf %lf", &p[i].x, &p[i].y, &p[i].z, &p[i].r);
		}
		printf("%.3lf\n", Prim());
	}
	return 0;
}