poj2031

简单题

#include < iostream >
#include < cstdio >
#include < cstdlib >
#include < cstring >
#include < cmath >
using namespace std;

#define maxn 105
#define eps 10E-9
#define inf 10000000

struct Point
{
double x, y, z, r;
} point[maxn];

double g[maxn][maxn];
int vis[maxn], n;
double lowc[maxn];

double dis(Point & a, Point & b)
{
Point c;
c.x = abs(a.x - b.x);
c.y = abs(a.y - b.y);
c.z = abs(a.z - b.z);
double ret = sqrt(c.x * c.x + c.y * c.y + c.z * c.z);
if (ret > a.r + b.r + eps)
return ret - a.r - b.r;
return 0 ;
}

void input()
{
for ( int i = 0 ; i < n; i ++ )
scanf( " %lf%lf%lf%lf " , & point[i].x, & point[i].y, & point[i].z,
& point[i].r);
for ( int i = 0 ; i < n; i ++ )
for ( int j = 0 ; j < n; j ++ )
g[i][j] = dis(point[i], point[j]);
}

double prim( double cost[][maxn], int n)
{
int i, j, p;
double minc, res = 0 ;
memset(vis, 0 , sizeof (vis));
vis[ 0 ] = 1 ;
for (i = 1 ; i < n; i ++ )
lowc[i] = cost[ 0 ][i];
for (i = 1 ; i < n; i ++ )
{
minc = inf;
p = - 1 ;
for (j = 0 ; j < n; j ++ )
if ( 0 == vis[j] && minc > lowc[j])
{
minc = lowc[j];
p = j;
}
if (inf == minc)
return - 1 ;
res += minc;
vis[p] = 1 ;
for (j = 0 ; j < n; j ++ )
if ( 0 == vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
return res;
}

int main()
{
// freopen("t.txt", "r", stdin);
while (scanf( " %d " , & n), n)
{
input();
double ans = prim(g, n);
printf( " %.3f\n " , ans);
}
return 0 ;
}