POJ 2031 Building a Space Station：三維球體最小生成樹 (Prim)

問題描述

給定 n ≤ 100 個球體（空間站單元），每球有中心 (x,y,z) 和半徑 r。球之間若接觸/重疊則已連通（距離 ≤ 0），否則需建走廊連接，成本為球面最短距離 max(0, dist - r1 - r2)。求連通所有球的最小走廊總長度。

建模為最小生成樹

• 節點：球體。
• 邊權：w(i,j) = max(0, distance(center_i, center_j) - r_i - r_j)。
• 求 MST 總權重即為答案。

Prim 算法實現（鄰接矩陣）

struct Node { double x,y,z,r; } p[105];
double dist(Node a, Node 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));
}
double w[105][105], d[105];
bool vis[105];

void prim(int n) {
    for (int i=1;i<=n;i++) d[i]=w[1][i], vis[i]=false;
    vis[1]=true; d[1]=0;
    double ans=0;
    for (int iter=1; iter