OD_2024_C卷_200分_7、5G网络建设【JAVA】【最小生成树】

package odjava;import java.util.Scanner;public class 七_5G网络建设 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 基站数量（节点数）int m = sc.nextInt(); // 基站对数量（边数）// 邻接矩阵int[][] graph = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 初始化默认各点之间互不联通，即i-j边权无限大graph[i][j] = Integer.MAX_VALUE;}}// 读取输入的基站对信息，并构建邻接矩阵for (int i = 0; i < m; i++) {int x = sc.nextInt(); // 基站1int y = sc.nextInt(); // 基站2int z = sc.nextInt(); // 基站间的距离int p = sc.nextInt(); // 是否已经联通的标志，0表示未联通，1表示已联通if (p == 0) {// x-y边权为zgraph[x][y] = z;graph[y][x] = z;} else {// 对应已经联通的两点，可以理解为边权为0graph[x][y] = 0;graph[y][x] = 0;}}// 输出最小生成树的边权和System.out.println(prim(graph, n));}/*** 使用 Prim 算法计算最小生成树的边权和** @param graph 邻接矩阵，表示图的连接关系* @param n     基站数量（节点数）* @return 最小生成树的边权和，如果无法形成最小生成树，则返回 -1*/public static int prim(int[][] graph, int n) {// 记录最小生成树的边权和int minWeight = 0;// inTree[i] 表示节点i是否在最小生成树中boolean[] inTree = new boolean[n + 1];// 初始时任选一个节点作为最小生成树的初始节点，这里选择节点1inTree[1] = true;// 记录最小生成树中点数量int inTree_count = 1;// dis[i]表示节点i到最小生成树集合的最短距离int[] dis = new int[n + 1];for (int i = 1; i <= n; i++) {// 初始时，最小生成树集合中只有节点1，因此其他节点到最小生成树的距离，其实就是到节点1的距离dis[i] = graph[1][i];}// 如果最小生成树中点数量达到n个，则结束循环while (inTree_count < n) {// 现在我们需要从未纳入最小生成树的点中，找到一个距离最小生成树最近的// minDis 记录这个最近距离int minDis = Integer.MAX_VALUE;// nodeIdx 记录距离最小生成树minDis个距离的节点int nodeIdx = 0;for (int i = 1; i <= n; i++) {// 从未纳入最小生成树的点中，找到一个距离最小生成树最近的if (!inTree[i] && dis[i] < minDis) {minDis = dis[i];nodeIdx = i;}}// 如果nodeIdx == 0，则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE，即不与最小生成树存在关联if (nodeIdx == 0) {// 则说明，当前所有点无法形成最小生成树return -1;}inTree[nodeIdx] = true; // 最小生成树需要纳入最短距离点nodeIdxinTree_count++; // 最小生成树中点数量+1minWeight += dis[nodeIdx]; // 更新最小生成树的权重和// 更新dis数组，使得dis[i]记录节点i到最小生成树的最短距离for (int i = 1; i <= n; i++) {if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {// 如果节点i到新节点nodeIdx的距离更近，则更新dis[i]dis[i] = graph[nodeIdx][i];}}}return minWeight;}
}