一 原问题链接

https://vjudge.net/problem/POJ-2031

https://vjudge.net/problem/POJ-2031

二 输入和输出

1 输入

数据由多个数据集组成。每个数据集的第1行都包含一个整数，表示单元的数量。以下 n 行是对单元的描述，其中第一行包含4个值，表示球体的中心坐标x、y和z，以及球体的半径 r,每个值都为小数。输入的结尾由包含 0 的行表示。

2 输出

对于每个数据集，都单行输出建造走廊的最短总长度。

注意：如果不需要建造走廊，则走廊的最短总长度为0.000

三 输入和输出样例

1 输入样例

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

2 输出样例

20.000

0.000

73.834

四 算法设计

本问题属于最小生成树问题，可以采用 Prim 或 Kruskal 算法求解。

1 计算任意两个单元之间的距离，如果两个单元有接触或重叠，则距离为 0.000

2 采用 Prim 算法求解最小生成树。

3 输出最小生成树的权值之和。

五 代码

package graph.poj2031;

import java.util.Scanner;

public class POJ2031 {
    static final int maxn = 105;
    static final double inf = 0x3f3f3f3f; // 类型double
    static double m[][] = new double[maxn][maxn];
    static double low[] = new double[maxn];
    static boolean vis[] = new boolean[maxn];
    static cell c[] = new cell[maxn];
    static int n;

    static double clu(cell c1, cell c2) {//计算两个球单元的距离
        double x = (c1.x - c2.x) * (c1.x - c2.x);
        double y = (c1.y - c2.y) * (c1.y - c2.y);
        double z = (c1.z - c2.z) * (c1.z - c2.z);
        double d = Math.sqrt(x + y + z);
        if (d - c1.r - c2.r <= 0)
            return 0.000;
        else
            return d - c1.r - c2.r;
    }

    static double prim(int s) {//返回值类型double
        for (int i = 0; i < n; i++)
            low[i] = m[s][i];
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
        vis[s] = true;
        double sum = 0.000;
        int t = 1;
        for (int i = 1; i < n; i++) {//执行n-1次
            double min = inf;
            for (int j = 0; j < n; j++) {//找最小
                if (!vis[j] && low[j] < min) {
                    min = low[j];
                    t = j;
                }
            }
            sum += min;
            vis[t] = true;
            for (int j = 0; j < n; j++) {//更新
                if (!vis[j] && low[j] > m[t][j])
                    low[j] = m[t][j];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            if (n == 0) {
                return;
            }

            for (int i = 0; i < c.length; i++) {
                c[i] = new cell();
            }

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (i == j)
                        m[i][j] = 0;
                    else
                        m[i][j] = inf;
            for (int i = 0; i < n; i++) {
                c[i].x = scanner.nextDouble();
                c[i].y = scanner.nextDouble();
                c[i].z = scanner.nextDouble();
                c[i].r = scanner.nextDouble();
            }

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    if (i != j)
                        m[i][j] = m[j][i] = clu(c[i], c[j]);
                }

            System.out.printf("%.3f\n", prim(0));
        }
    }
}

// 球形单元的圆心，半径
class cell {
    double x;
    double y;
    double z;
    double r;
}

六 测试

绿色为输入，白色为输出。