不比一致。在空间站成功的进入轨道后每个单间被固定在预定的位置上。很奇怪的是，两个单间可以接触，甚至可以重叠，在极端的情况下，一个单间甚至可以完全包含另一个单间。
所有的单间都必须连接，因为宇航员可以从一个单间走到另一个单间。在以下情形，宇航员可以从单间A走到单间B。
（1）A和B接触，或者重叠。
（2）A和B用一个走廊连接。
（3）存在单间C，是的从A走到C，也可以从B走到C。
如果要求安排设计空间站的结构，也就是安排哪些单间需要用走廊连接。在设计走廊的结构时有一定的自由性。修建走廊的费用正比于它的长度。因此，需要选择一个方案，使得走廊的总长度最短。走廊修建在两个单间的表面，且假设任意两条走廊都不交叉。
分析：
首先求出所有的单间两两是否接触如果接触，说明他们之间的边长为0，不接触那么就是圆心的距离减去两个单间的半径。然后构图求最小生成树，采用Kruskal算法。
代码：
#include
#include
#include
#include
#include
using namespace std; #define maxm 5050 #define maxn 110 int m, parent[maxn]; double ans; struct ball { double x, y, z, r; }BL[maxn]; double dis(ball a, ball b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-a.r-b.r; } struct edge { int u, v; double w; }EG[maxm]; bool cmp(edge a, edge b) { return a.w < b.w; } int Find(int x) { if(parent[x] == -1) return x; return Find(parent[x]); } void Kruskal() { memset(parent, -1, sizeof(parent)); ans = 0; sort(EG, EG+m, cmp); for(int i = 0; i < m; i++) { int t1 = Find(EG[i].u), t2 = Find(EG[i].v); if(t1 != t2) { ans += EG[i].w; parent[t1] = t2; } } } int main() { int n; while(scanf("%d", &n), n) { for(int i = 0; i < n; ++i) scanf("%lf%lf%lf%lf", &BL[i].x, &BL[i].y, &BL[i].z, &BL[i].r); m = 0; for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j) { double d = dis(BL[i], BL[j]); EG[m].u = i; EG[m].v = j; if(d > 0) EG[m].w = d; else EG[m].w = 0; ++m; } Kruskal(); printf("%.3lf\n", ans); } return 0; }