题目描述

你是空间站工程团队的一员，负责在空间站建造过程中完成一项编程任务。

空间站由多个单元舱（cell）组成，所有单元舱均为球形，但尺寸不一定相同。每个单元舱在空间站成功入轨后即被固定在预定位置。奇特的是，两个单元舱可能相互接触甚至部分重叠，极端情况下一个单元舱可能完全包裹另一个单元舱。

所有单元舱必须保持连通性，以确保宇航员能在任意两个单元舱之间通行。通行规则如下：

1. 直接连通：单元舱$A$与$B$接触或重叠。
2. 走廊连接：通过建造**走廊（corridor）**连接$A$和$B$。
3. 间接连通：存在单元舱$C$，使得$A$与$C$、$B$与$C$均连通（满足传递性）。

任务要求

设计走廊的连接方案，使得：

• 所有单元舱连通。
• 总走廊长度最短（走廊成本与其长度成正比）。
• 走廊可视为无宽度的直线，连接两单元舱表面，且长度取最短可能值。
• 若无需走廊即可连通（如所有单元舱已直接接触/重叠），输出$0.000$。

输入格式

• 每个测试用例格式如下：

  n
  x1 y1 z1 r1
  x2 y2 z2 r2
  ...
  xn yn zn rn
  

  • $n$：单元舱数量（$1 \leq n \leq 100$）。
  • $x_i, y_i, z_i$：第$i$个单元舱中心的三维坐标（保留$3$位小数）。
  • $r_i$：第$i$个单元舱的半径（保留$3$位小数）。
  • 坐标和半径均为正数且小于$100.0$。
• 输入以单独一行的$0$结束。

输出格式

对每个测试用例，输出一行：最短走廊总长度（保留$3$位小数，误差不超过$0.001$）。

示例

输入：

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

输出：

20.000
0.000
73.834

关键概念

• 走廊长度计算：两单元舱$A$和$B$的走廊长度为$\max(0, \text{distance}(A_{\text{center}}, B_{\text{center}}) - (r_A + r_B))$。
• 最小生成树（MST）：将单元舱视为节点，走廊视为边，使用Kruskal或Prim算法求解最短总走廊长度。

解题思路

1. 计算单元舱间距离：若两舱中心距离$\leq r_A + r_B$，则无需走廊（边权为$0$）。
2. 构建完全图：以单元舱为顶点，以走廊长度为边权。
3. 求解MST：使用贪心算法选择边，确保连通性的同时最小化总长度。

代码实现

#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
double dis[105][105];
int n;
struct cod
{
	double x,y,z,r;
}s[105];
void prim()
{
	int vis[105],i;
	double sum,dist[105];
	memset(vis,0,sizeof(vis));
	memset(dist,0,sizeof(dist));
	for(i=1;i<n;i++)
		dist[i]=dis[0][i];
	vis[0]=1;
	while(1)
	{
		double min=inf;
		int k=0;
		for(i=1;i<n;i++)
			if(dist[i]<min&&!vis[i])
			{
				k=i;
				min=dist[i];
			}
		if(k==0)
			break;
		vis[k]=1;
		for(i=1;i<n;i++)
			if(dist[i]>dis[k][i]&&!vis[i])
				dist[i]=dis[k][i];
	}
	for(i=1,sum=0;i<n;i++)
		sum+=dist[i];
	printf("%.3lf\n",sum);
}
int main()
{
	int i,j;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;i++)
			scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z,&s[i].r);
		memset(dis,0,sizeof(dis));
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
			{
					dis[i][j]=dis[j][i]=sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)+(s[i].z-s[j].z)*(s[i].z-s[j].z))-s[i].r-s[j].r;
					if(dis[i][j]<0)
						dis[i][j]=dis[j][i]=0;
			}
		prim();
	}
	return 0;
 }