蓝桥杯20534爆破 java

这道题本质是最小生成树（MST）问题

这道题的模型是：

我们可以用Prim 算法，该算法的核心是从一个起点开始，逐步将距离当前连通集合最近的节点加入集合，最终形成最小生成树。

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//创建数组存放圆的数据
int[][] circle = new int[n][3];
for (int i = 0; i < circle.length; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int r = sc.nextInt();
circle[i][0] = x;
circle[i][1] = y;
circle[i][2] = r;
}
sc.close();
// 构建邻接矩阵：graph[i][j]表示顶点i到j的边权
double[][] graph = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) { //表示为同一个魔法阵
graph[i][j] = 0;
} else {
int x1 = circle[i][0], y1 = circle[i][1], r1 = circle[i][2];
int x2 = circle[j][0], y2 = circle[j][1], r2 = circle[j][2];
double dist = Math.sqrt(Math.pow(x1 – x2, 2) + Math.pow(y1 – y2, 2));
// 边权：相交则为0，否则为“距离 – 两半径之和”
graph[i][j] = Math.max(0, dist – r1 – r2);
}
}
}
// Prim算法初始化
double[] dist = new double[n]; // 记录每个顶点到当前生成树的最小距离
Arrays.fill(dist, Double.MAX_VALUE);
boolean[] visited = new boolean[n];// 标记顶点是否已加入生成树
dist[0] = 0;// // 从顶点0开始构建生成树
visited[0] = true; // 标记顶点0已加入生成树
// 初始化距离数组为从顶点0出发的边权
for (int v = 0; v < n; v++) {
dist[v] = graph[0][v];
}
double totalLength = 0;// 记录最小生成树的总权重
for (int i = 1; i < n ; i++) { // 生成树需要n-1条边
// 找到“未访问且距离当前生成树最近”的顶点u
int u = -1;
double minDist = Double.MAX_VALUE;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}

visited[u] = true; // 将u加入生成树
totalLength += minDist; // 累加边权

// 更新其他未访问顶点到生成树的最小距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
}
}
}
System.out.println( String.format("%.2f", totalLength));
}
}