class061 最小生成树【算法】

2023-12-8 11:48:12

算法讲解061【必备】最小生成树

在这里插入图片描述

code1 P3366 【模板】最小生成树

// Kruskal算法模版（洛谷）
// 静态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

package class061;

// Kruskal算法模版（洛谷）
// 静态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
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.Arrays;

// 时间复杂度O(m * log m) + O(n + m)
public class Code01_Kruskal {

	public static int MAXN = 5001;

	public static int MAXM = 200001;

	public static int[] father = new int[MAXN];

	// u, v, w
	public static int[][] edges = new int[MAXM][3];

	public static int n, m;

	public static void build() {
		for (int i = 1; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果x和y本来就是一个集合，返回false
	// 如果x和y不是一个集合，合并之后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build();
			for (int i = 0; i < m; i++) {
				in.nextToken();
				edges[i][0] = (int) in.nval;
				in.nextToken();
				edges[i][1] = (int) in.nval;
				in.nextToken();
				edges[i][2] = (int) in.nval;
			}
			Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
			int ans = 0;
			int edgeCnt = 0;
			for (int[] edge : edges) {
				if (union(edge[0], edge[1])) {
					edgeCnt++;
					ans += edge[2];
				}
			}
			out.println(edgeCnt == n - 1 ? ans : "orz");
		}
		out.flush();
		out.close();
		br.close();
	}

}

code2 P3366 【模板】最小生成树

// Prim算法模版（洛谷）
// 动态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

package class061;

// Prim算法模版（洛谷）
// 动态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

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.PriorityQueue;

// 时间复杂度O(n + m) + O(m * log m)
public class Code02_PrimDynamic {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
			int n = (int) in.nval;
			for (int i = 0; i <= n; i++) {
				graph.add(new ArrayList<>());
			}
			in.nextToken();
			int m = (int) in.nval;
			for (int i = 0, u, v, w; i < m; i++) {
				in.nextToken();
				u = (int) in.nval;
				in.nextToken();
				v = (int) in.nval;
				in.nextToken();
				w = (int) in.nval;
				graph.get(u).add(new int[] { v, w });
				graph.get(v).add(new int[] { u, w });
			}
			// int[] record
			// record[0] : 到达的节点
			// record[1] : 到达的花费
			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]) {
					nodeCnt++;
					set[next] = true;
					ans += cost;
					for (int[] e : graph.get(next)) {
						heap.add(e);
					}
				}
			}
			out.println(nodeCnt == n ? ans : "orz");
		}
		out.flush();
		out.close();
		br.close();
	}

}

code2 P3366 【模板】最小生成树

// 建图用链式前向星
// 堆也是用数组结构手写的、且只和节点个数有关
// 这个实现留给有需要的同学
// 但是一般情况下并不需要做到这个程度

package class061;

// Prim算法优化（洛谷）
// 静态空间实现
// 时间复杂度O(n + m) + O((m+n) * log n)
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

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.Arrays;

// 建图用链式前向星
// 堆也是用数组结构手写的、且只和节点个数有关
// 这个实现留给有需要的同学
// 但是一般情况下并不需要做到这个程度

public class Code02_PrimStatic {

	public static int MAXN = 5001;

	public static int MAXM = 400001;

	public static int n, m;

	// 链式前向星建图
	public static int[] head = new int[MAXN];

	public static int[] next = new int[MAXM];

	public static int[] to = new int[MAXM];

	public static int[] weight = new int[MAXM];

	public static int cnt;

	// 改写的堆结构
	public static int[][] heap = new int[MAXN][2];

	// where[v] = -1，表示v这个节点，从来没有进入过堆
	// where[v] = -2，表示v这个节点，已经弹出过了
	// where[v] = i(>=0)，表示v这个节点，在堆上的i位置
	public static int[] where = new int[MAXN];

	// 堆的大小
	public static int heapSize;

	// 找到的节点个数
	public static int nodeCnt;

	public static void build() {
		cnt = 1;
		heapSize = 0;
		nodeCnt = 0;
		Arrays.fill(head, 1, n + 1, 0);
		Arrays.fill(where, 1, n + 1, -1);
	}

	public static void addEdge(int u, int v, int w) {
		next[cnt] = head[u];
		to[cnt] = v;
		weight[cnt] = w;
		head[u] = cnt++;
	}

	// 当前处理的是编号为ei的边！
	public static void addOrUpdateOrIgnore(int ei) {
		int v = to[ei];
		int w = weight[ei];
		// 去往v点，权重w
		if (where[v] == -1) {
			// v这个点，从来没有进入过堆！
			heap[heapSize][0] = v;
			heap[heapSize][1] = w;
			where[v] = heapSize++;
			heapInsert(where[v]);
		} else if (where[v] >= 0) {
			// v这个点的记录，在堆上的位置是where[v]
			heap[where[v]][1] = Math.min(heap[where[v]][1], w);
			heapInsert(where[v]);
		}
	}

	public static void heapInsert(int i) {
		while (heap[i][1] < heap[(i - 1) / 2][1]) {
			swap(i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}

	public static int u;

	public static int w;

	// 堆顶的记录：节点 -> u、到节点的花费 -> w
	public static void pop() {
		u = heap[0][0];
		w = heap[0][1];
		swap(0, --heapSize);
		heapify(0);
		where[u] = -2;
		nodeCnt++;
	}

	public static void heapify(int i) {
		int l = 1;
		while (l < heapSize) {
			int best = l + 1 < heapSize && heap[l + 1][1] < heap[l][1] ? l + 1 : l;
			best = heap[best][1] < heap[i][1] ? best : i;
			if (best == i) {
				break;
			}
			swap(best, i);
			i = best;
			l = i * 2 + 1;
		}
	}

	public static boolean isEmpty() {
		return heapSize == 0;
	}

	// 堆上，i位置的信息 和 j位置的信息 交换！
	public static void swap(int i, int j) {
		int a = heap[i][0];
		int b = heap[j][0];
		where[a] = j;
		where[b] = i;
		int[] tmp = heap[i];
		heap[i] = heap[j];
		heap[j] = tmp;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build();
			for (int i = 0, u, v, w; i < m; i++) {
				in.nextToken();
				u = (int) in.nval;
				in.nextToken();
				v = (int) in.nval;
				in.nextToken();
				w = (int) in.nval;
				addEdge(u, v, w);
				addEdge(v, u, w);
			}
			int ans = prim();
			out.println(nodeCnt == n ? ans : "orz");
		}
		out.flush();
		out.close();
		br.close();
	}

	public static int prim() {
		// 1节点出发
		nodeCnt = 1;
		where[1] = -2;
		for (int ei = head[1]; ei > 0; ei = next[ei]) {
			addOrUpdateOrIgnore(ei);
		}
		int ans = 0;
		while (!isEmpty()) {
			pop();
			ans += w;
			for (int ei = head[u]; ei > 0; ei = next[ei]) {
				addOrUpdateOrIgnore(ei);
			}
		}
		return ans;
	}

}

code3 1168.水资源分配优化

// 水资源分配优化
// 村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
// 对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
// 成本为 wells[i - 1] （注意 -1 ，因为索引从0开始）
// 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
// 其中每个 pipes[j] = [house1j, house2j, costj]
// 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
// 请返回为所有房子都供水的最低总成本
// 测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/

题目：
1168水资源分配优化Plus
困难

村里面一共有n栋房子。我们希望通过建造水和铺设管道来为所有房子供水。

对于每个房子i，我们有两种可选的供水方案:
一种是直接在房子内建造水井，成本为 wells[i - 1] (注意-1，因为索引从0开始);
另一种是从另一口井铺设管道引水，数组pipes给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j，house2j，costj]代表用管道
将house1j和house2j连接在一起的成本。连接是双向的。

请返回为所有房子都供水的最低总成本

假定有一个水源连接着所有房子，对应边的权重就是wells，
在采用最小生成树算法，把连接水源的权值最小求出来。

示例一
输入:n =3，wells = [1,2,2]，pipes =[[1,2,1],[2,3,1l]
输出:3
解释:
上图展示了铺设管道连接房屋的成本最好的策略是在第一个房子里建造水井(成本为 1)，
然后将其他房子铺设管道连起来(成本为 2)，所以总成本为3

示例 2:
输入:n = 2，wells = [1,1]，pipes =[[1,2,11]
输出:2
解释:我们可以用以下三种方法中的一种来提供低成本的水:
选项1:
在1号房子里面建一口井，成本为1
在房子2内建造井，成本为1
总成本是2。
选项2:
在1号房子里面建一口井，成本为1
花费1连接房子2和房子1。
总成本是2。
选项3:
在房子2内建造井，成本为1
花费1连接房子1和房子2
总成本是2。
注意，我们可以用cost 1或cost 2连接房子1和房子2
但我们总是选择最便宜的选项。

提示:

2<=n<= 10⁴
wells.length == n
0<= wells[i] <= 10⁵
1<= pipes.length <= 10⁴
pipes[j].length == 3
1 <= house1_j , house2_j <= n
0<= cost_j <= 10⁵
house1_j != house2_j

package class061;

import java.util.Arrays;

// 水资源分配优化
// 村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
// 对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
// 成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
// 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
// 其中每个 pipes[j] = [house1j, house2j, costj] 
// 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
// 请返回 为所有房子都供水的最低总成本
// 测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/
public class Code03_OptimizeWaterDistribution {

	public static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
		build(n);
		for (int i = 0; i < n; i++, cnt++) {
			// wells : 100   30
			//         0(1)  1(2)
			edges[cnt][0] = 0;
			edges[cnt][1] = i + 1;
			edges[cnt][2] = wells[i];
		}
		for (int i = 0; i < pipes.length; i++, cnt++) {
			edges[cnt][0] = pipes[i][0];
			edges[cnt][1] = pipes[i][1];
			edges[cnt][2] = pipes[i][2];
		}
		Arrays.sort(edges, 0, cnt, (a, b) -> a[2] - b[2]);
		int ans = 0;
		for (int i = 0; i < cnt; i++) {
			if (union(edges[i][0], edges[i][1])) {
				ans += edges[i][2];
			}
		}
		return ans;
	}

	public static int MAXN = 10010;

	public static int[][] edges = new int[MAXN << 1][3];

	public static int cnt;

	public static int[] father = new int[MAXN];

	public static void build(int n) {
		cnt = 0;
		for (int i = 0; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果x和y，原本是一个集合，返回false
	// 如果x和y，不是一个集合，合并之后后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}

}

code4 1697. 检查边长度限制的路径是否存在

// 检查边长度限制的路径是否存在
// 给你一个 n 个点组成的无向图边集 edgeList
// 其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
// 请注意，两个点之间可能有超过一条边。
// 给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
// 你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
// 且这条路径上的每一条边都严格小于 limitj 。
// 请你返回一个布尔数组 answer ，其中 answer.length == queries.length
// 当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false
// 测试链接 : https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/

package class061;

import java.util.Arrays;

// 检查边长度限制的路径是否存在
// 给你一个 n 个点组成的无向图边集 edgeList
// 其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
// 请注意，两个点之间可能有 超过一条边 。
// 给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
// 你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
// 且这条路径上的每一条边都 严格小于 limitj 。
// 请你返回一个 布尔数组 answer ，其中 answer.length == queries.length
// 当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false
// 测试链接 : https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/
public class Code04_CheckingExistenceOfEdgeLengthLimit {

	public static boolean[] distanceLimitedPathsExist(int n, int[][] edges, int[][] queries) {
		Arrays.sort(edges, (a, b) -> a[2] - b[2]);
		int m = edges.length;
		int k = queries.length;
		for (int i = 0; i < k; i++) {
			questions[i][0] = queries[i][0];
			questions[i][1] = queries[i][1];
			questions[i][2] = queries[i][2];
			questions[i][3] = i;
		}
		Arrays.sort(questions, 0, k, (a, b) -> a[2] - b[2]);
		build(n);
		boolean[] ans = new boolean[k];
		for (int i = 0, j = 0; i < k; i++) {
			// i : 问题编号
			// j : 边的编号
			for (; j < m && edges[j][2] < questions[i][2]; j++) {
				union(edges[j][0], edges[j][1]);
			}
			ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
		}
		return ans;
	}

	public static int MAXN = 100001;

	public static int[][] questions = new int[MAXN][4];

	public static int[] father = new int[MAXN];

	public static void build(int n) {
		for (int i = 0; i < n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	public static boolean isSameSet(int x, int y) {
		return find(x) == find(y);
	}

	public static void union(int x, int y) {
		father[find(x)] = find(y);
	}

}

code5 P2330 [SCOI2005] 繁忙的都市

// 繁忙的都市
// 一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造
// 城市的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连
// 两个交叉路口之间最多有一条道路相连接，这些道路是双向的
// 且把所有的交叉路口直接或间接的连接起来了
// 每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造
// 但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
// 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
// 2. 在满足要求1的情况下，改造的道路尽量少
// 3. 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小
// 作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建
// 返回选出了几条道路以及分值最大的那条道路的分值是多少
// 测试链接 : https://www.luogu.com.cn/problem/P2330
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

package class061;

// 繁忙的都市
// 一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造
// 城市的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连
// 两个交叉路口之间最多有一条道路相连接，这些道路是双向的
// 且把所有的交叉路口直接或间接的连接起来了
// 每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造
// 但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
// 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
// 2. 在满足要求1的情况下，改造的道路尽量少
// 3. 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小
// 作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建
// 返回选出了几条道路 以及 分值最大的那条道路的分值是多少
// 测试链接 : https://www.luogu.com.cn/problem/P2330
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过

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.Arrays;

public class Code05_BusyCities {

	public static int MAXN = 301;

	public static int MAXM = 8001;

	public static int[] father = new int[MAXN];

	public static int[][] edges = new int[MAXM][3];

	public static int n, m;

	public static void build() {
		for (int i = 1; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果x和y本来就是一个集合，返回false
	// 如果x和y不是一个集合，合并之后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build();
			for (int i = 0; i < m; i++) {
				in.nextToken();
				edges[i][0] = (int) in.nval;
				in.nextToken();
				edges[i][1] = (int) in.nval;
				in.nextToken();
				edges[i][2] = (int) in.nval;
			}
			Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
			int ans = 0;
			int edgeCnt = 0;
			for (int[] edge : edges) {
				if (union(edge[0], edge[1])) {
					edgeCnt++;
					ans = Math.max(ans, edge[2]);
				}
				if (edgeCnt == n - 1) {
					break;
				}
			}
			out.println((n - 1) + " " + ans);
		}
		out.flush();
		out.close();
		br.close();
	}

}