2790041_ac_15ms_172k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
# define MAX 101
# define INF 2100000000

double W;
double cost[MAX][MAX];

struct node
{
	double x, y, z, r;
}pot[101];

void prim(int n,int v)
{
	int i, j, k;
	double min;
	double lowcost[MAX];

	W = 0;
	for(i = 0; i < n; i++)
		lowcost[i] = cost[v][i];
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=-1&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			W += min;
			lowcost[k] = -1;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=-1&&cost[k][j]<lowcost[j])
				lowcost[j] = cost[k][j];
	}
	printf("%.3lf\n",W);
}

double dis(int i,int j)
{
	return sqrt((pot[i].x-pot[j].x)*(pot[i].x-pot[j].x)+(pot[i].y-pot[j].y)*(pot[i].y-pot[j].y)+(pot[i].z-pot[j].z)*(pot[i].z-pot[j].z));
}

void init(int n)
{
	int i, j;
	double tmp;

	for(i = 0; i < n; i++)
		scanf("%lf%lf%lf%lf",&pot[i].x,&pot[i].y,&pot[i].z,&pot[i].r);
	for(i = 0; i < n; i++)
	{
		cost[i][i] = -1;
		for(j = i+1; j < n; j++)
		{
			tmp = dis(i,j);
			if(tmp > pot[i].r+pot[j].r)
				cost[i][j] = cost[j][i] = tmp-(pot[i].r+pot[j].r);
			else
				cost[i][j] = cost[j][i] = 0;
		}
	}
}
int main()
{
	int n;

	while(scanf("%d",&n)==1,n)
	{
		init(n);
		prim(n,0);
	}
	return 1;
}