P3366 【模板】最小生成树(Prim算法)

本文主要是介绍P3366 【模板】最小生成树(Prim算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: P3366 【模板】最小生成树

思路

这是一个求最小生成树的问题。给定一个无向图，需要找到连接所有节点的最小权重边集合。如果图不连通，则输出"orz"。
最小生成树是一棵包含图中所有节点的树，且树中的边的权重之和最小。常用的算法有Prim算法和Kruskal算法。

解题方法

本题可以使用Prim算法来解决。Prim算法的基本思想是从一个起始节点开始，每次选择一个与当前生成树相连的权重最小的边，将其加入生成树中，直到生成树包含了所有节点。
具体步骤如下：

1. 创建一个优先队列（最小堆）用于存储待选边，初始时将起始节点的所有边加入队列。
2. 创建一个布尔数组用于标记节点是否已经加入生成树，初始时只有起始节点被标记为已加入。
3. 创建一个变量用于记录已加入生成树的节点数量，初始时为1。
4. 创建一个变量用于记录最小生成树的总权重，初始时为0。
5. 循环执行以下步骤，直到生成树包含了所有节点：

• 从优先队列中取出权重最小的边，记为当前边。
• 如果当前边的另一个节点未加入生成树，则将该节点加入生成树，并将节点数量加1，将当前边的权重加入总权重。
• 将当前边的另一个节点的所有边加入优先队列。

6. 判断生成树的节点数量是否等于图中的节点数量，如果相等，则输出最小生成树的总权重，否则输出"orz"。

复杂度

时间复杂度:

时间复杂度：Prim算法的时间复杂度为$O((V+E)logV)$，其中V为节点数量，E为边数量。

空间复杂度:

空间复杂度：Prim算法的空间复杂度为$O(V)$，其中V为节点数量。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = 5010;static int MAXM = 200010;static int n, m;public static void main(String[] args) throws IOException {List<List<int[]>> graph = new ArrayList<>();n = nextInt();m = nextInt();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 0, f, t, w; i < m; i++) {f = nextInt();t = nextInt();w = nextInt();graph.get(f).add(new int[] { t, w });graph.get(t).add(new int[] { f, w });}PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);for (int[] edge : graph.get(1)) {heap.add(edge);}boolean[] set = new boolean[n + 1];int nodeCnt = 1;set[1] = true;int ans = 0;while(!heap.isEmpty()) {int[] edge = heap.poll();int next = edge[0];int cost = edge[1];if(!set[next]) {set[next] = true;nodeCnt++;ans += cost;for(int[] e : graph.get(next)) {heap.add(e);}}}out.println(nodeCnt == n ? ans : "orz");out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}

这篇关于P3366 【模板】最小生成树(Prim算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---