普通建站,iis 新建网站,网站规划的任务,网络系统的价值跟用户数量的关系class061 最小生成树【算法】
2023-12-8 11:48:12
算法讲解061【必备】最小生成树 code1 P3366 【模板】最小生成树
// Kruskal算法模版#xff08;洛谷#xff09; // 静态空间实现 // 测试链接 : https://www.luogu.com.cn/problem/P3366 // 请同学们务必参考如下代码中…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, wpublic 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不是一个集合合并之后返回truepublic 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) {ArrayListArrayListint[] 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] : 到达的花费PriorityQueueint[] 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((mn) * 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点权重wif (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、到节点的花费 - wpublic 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] [house1jhouse2jcostj]代表用管道 将house1j和house2j连接在一起的成本。连接是双向的。
请返回为所有房子都供水的最低总成本
假定有一个水源连接着所有房子对应边的权重就是wells 在采用最小生成树算法把连接水源的权值最小求出来。
示例一
输入:n 3wells [1,2,2]pipes [[1,2,1],[2,3,1l]
输出:3
解释:
上图展示了铺设管道连接房屋的成本最好的策略是在第一个房子里建造水井(成本为 1)
然后将其他房子铺设管道连起来(成本为 2)所以总成本为3示例 2:
输入:n 2wells [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
但我们总是选择最便宜的选项。
提示:
2n 104wells.length n0 wells[i] 1051 pipes.length 104pipes[j].length 31 house1j , house2j n0 costj 105house1j ! house2j
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不是一个集合合并之后后返回truepublic 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不是一个集合合并之后返回truepublic 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();}}
2023-12-8 14:22:17
