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(); // 基站1
            int y = sc.nextInt(); // 基站2
            int z = sc.nextInt(); // 基站间的距离
            int p = sc.nextInt(); // 是否已经联通的标志，0表示未联通，1表示已联通

            if (p == 0) {
                // x-y边权为z
                graph[x][y] = z;
                graph[y][x] = z;
            } else {
                // 对应已经联通的两点，可以理解为边权为0
                graph[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];

        // 初始时任选一个节点作为最小生成树的初始节点，这里选择节点1
        inTree[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; // 最小生成树需要纳入最短距离点nodeIdx
            inTree_count++; // 最小生成树中点数量+1
            minWeight += 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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108