织梦怎么设置网站首页,百度的竞价排名是哪种方式,ps做营销型网站布局,商洛免费做网站公司#x1f389;#x1f389;欢迎光临#x1f389;#x1f389; #x1f3c5;我是苏泽#xff0c;一位对技术充满热情的探索者和分享者。#x1f680;#x1f680; #x1f31f;特别推荐给大家我的最新专栏《数据结构与算法#xff1a;初学者入门指南》#x1f4d8;欢迎光临 我是苏泽一位对技术充满热情的探索者和分享者。 特别推荐给大家我的最新专栏《数据结构与算法初学者入门指南》 希望能和大家一起学习共同进步 这是苏泽的个人主页可以看到我其他的内容哦 努力的苏泽http://suzee.blog.csdn.net 当谈论并查集时我们可以继续使用上述的动物园比喻来解释它的概念。
我们可以把并查集看作是一个动物园管理系统帮助你管理动物们的归属关系。
在这个动物园中每个动物都有一个独特的编号代表一个独立的元素。一开始每个动物都是独立的没有与其他动物建立关系。 初始化Init()函数就像是给每个动物分配一个编号和一个独立的笼子。这样它们就有了一个起始的归属地。 查找函数Find()函数就像是动物们在寻找自己所属的笼子。当你给一个动物的编号它会告诉你它所在的笼子。这样你可以快速找到任何动物所属的笼子。 合并集合函数Join()函数就像是把两个笼子合并在一起让两个动物的集合变成一个更大的集合。当你把两个动物放在同一个笼子里它们就成为了同一个集合共享同一个归属地。 class UnionFind {private int[] parent;public UnionFind(int size) {parent new int[size];for (int i 0; i size; i) {parent[i] i; // 每个动物初始时独立成为一个集合自己是自己的根节点}}public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]); // 使用路径压缩优化将当前动物的父节点直接指向根节点}return parent[x]; // 返回动物所属的笼子根节点}public void join(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {parent[rootX] rootY; // 将两个笼子合并让一个根节点指向另一个根节点}}
} 历届试题 国王的烦恼 问题描述 C 国由 n nn 个小岛组成为了方便小岛之间联络C 国在小岛间建立了 m mm 座大桥每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而由于海水冲刷有一些大桥面临着不能使用的危险。 如果两个小岛间的所有大桥都不能使用则这两座小岛就不能直接到达了。然而只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达他们就会安然无事。但是如果前一天两个小岛之间还有方法可以到达后一天却不能到达了居民们就会一起抗议。 现在 C 国的国王已经知道了每座桥能使用的天数超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。 输入格式 输入的第一行包含两个整数 n , m n, mn,m分别表示小岛的个数和桥的数量。 接下来 m mm 行每行三个整数 a , b , t a, b, ta,b,t分别表示该座桥连接 a aa 号和 b bb 号两个小岛能使用t天。小岛的编号从 1 开始递增。 输出格式 输出一个整数表示居民们会抗议的天数。 样例输入 4 4 1 2 2 1 3 2 2 3 1 3 4 3 样例输出 2 样例说明 第一天后 2 和 3 之间的桥不能使用不影响。 第二天后 1 和 2 之间以及1和3之间的桥不能使用居民们会抗议。 第三天后 3 和 4 之间的桥不能使用居民们会抗议。 数据规模和约定 对于 30% 的数据1 ≤ n ≤ 20 1 ≤ m ≤ 100 1\leq n \leq 201 \leq m \leq 1001≤n≤201≤m≤100 对于 50% 的数据1 ≤ n ≤ 500 1 ≤ m ≤ 10000 1 \leq n \leq 5001 \leq m \leq 100001≤n≤5001≤m≤10000 对于 100% 的数据1 ≤ n ≤ 10000 1 ≤ m ≤ 100000 1 ≤ a , b ≤ n 1 ≤ t ≤ 100000 1 \leq n \leq 100001 \leq m \leq 1000001\leq a, b \leq n 1 \leq t \leq 1000001≤n≤100001≤m≤1000001≤a,b≤n1≤t≤100000。 首先我们需要根据输入的桥的信息构建并查集。
对于每座桥如果它的使用天数超过了指定的天数我们将这两个小岛合并成同一个集合。如果它的使用天数没有超过指定的天数说明这座桥可以使用我们不需要对这两个小岛进行合并。
接下来我们遍历所有的桥对于每座桥我们查找连接的两个小岛是否属于同一个集合。如果不属于同一个集合说明这两个小岛之间没有其他路径可以到达居民们会抗议的天数加一。
最后输出居民们会抗议的天数即可。
import java.util.*;class UnionFind {private int[] parent;public UnionFind(int size) {parent new int[size 1];for (int i 1; i size; i) {parent[i] i;}}public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {parent[rootX] rootY;}}
}public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();UnionFind uf new UnionFind(n);for (int i 0; i m; i) {int a scanner.nextInt();int b scanner.nextInt();int t scanner.nextInt();if (t 2) {uf.union(a, b);}}int protestDays 0;for (int i 1; i n; i) {if (uf.find(i) i) {protestDays;}}System.out.println(protestDays - 1);}
}
第二道题 问题描述 小蓝国是一个水上王国, 有 2021 个城邦, 依次编号 1 到 2021。在任意两 个城邦之间, 都有一座桥直接连接。 为了庆祝小蓝国的传统节日, 小蓝国政府准备将一部分桥装饰起来。 对于编号为 a 和 b 的两个城邦, 它们之间的桥如果要装饰起来, 需要的费 用如下计算: 找到 a 和 b 在十进制下所有不同的数位, 将数位上的数字求和。 例如, 编号为 2021 和 922 两个城邦之间, 千位、百位和个位都不同, 将这些数位上的数字加起来是 (201)(092)14 。注意 922 没有千位, 千位看成 0 。 为了节约开支, 小蓝国政府准备只装饰 2020 座桥, 并且要保证从任意一个 城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。 请问, 小蓝国政府至少要花多少费用才能完成装饰。 提示: 建议使用计算机编程解决问题。 答案提交 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。 这道题有两个思路
1.动态规划
思路讲解
首先我们定义一个二维数组dp其中dp[i][j]表示城邦i到城邦j之间需要装饰的费用。
然后我们可以使用动态规划的思路来计算dp数组的值。对于每对城邦(i, j)我们可以通过考虑最后一段路径(i, k, j)来计算dp[i][j]的值其中k是城邦j的前一个城邦。
具体地我们可以遍历城邦k的所有可能取值从1到2021然后计算dp[i][j]的值。我们可以将dp[i][j]初始化为dp[i][k] dp[k][j]然后再添加城邦k和j之间的装饰费用cost(k, j)。其中cost(k, j)可以通过将城邦k和j的编号转换为字符串然后遍历字符串中的每个字符将字符转换为数字并求和得到。
最后我们需要计算小蓝国政府至少要花费的费用即dp[1][2021]。
public class Main {public static int calculateCost(int x, int y) {String strX String.valueOf(x);String strY String.valueOf(y);int cost 0;for (char digit : strX.toCharArray()) {if (strY.contains(String.valueOf(digit))) {cost Character.getNumericValue(digit);}}return cost;}public static void main(String[] args) {int[][] dp new int[2022][2022];for (int i 1; i 2021; i) {for (int j 1; j 2021; j) {if (i ! j) {dp[i][j] calculateCost(i, j);}}}for (int k 1; k 2021; k) {for (int i 1; i 2021; i) {for (int j 1; j 2021; j) {if (i ! j i ! k j ! k) {dp[i][j] Math.min(dp[i][j], dp[i][k] dp[k][j]);}}}}int answer dp[1][2021];System.out.println(answer);}
}
2.并查集
题目将城堡看作连通带权无向图其中城堡的编号表示图的节点城堡之间的桥梁装饰费用表示图的边权。
首先我们定义一个并查集数据结构用于合并城堡所属的连通分量。
然后我们遍历所有的桥梁计算每座桥梁的装饰费用并将费用作为边权存储在一个二维数组dp中。
接下来我们使用并查集的思想将连接费用为0的城堡合并到同一个连通分量中。
最后我们计算所有城堡到第一个城堡的装饰费用即累加每个连通分量中的最小边权。
这样我们就可以得到小蓝国政府至少要花费的费用。
import java.util.Arrays;public class Main {public static class UnionFind {private int[] parent;private int[] rank;public UnionFind(int n) {parent new int[n];rank new int[n];Arrays.fill(rank, 1);for (int i 0; i n; i) {parent[i] i;}}public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {if (rank[rootX] rank[rootY]) {parent[rootY] rootX;} else if (rank[rootX] rank[rootY]) {parent[rootX] rootY;} else {parent[rootY] rootX;rank[rootX];}}}}public static int calculateCost(int x, int y) {String strX String.valueOf(x);String strY String.valueOf(y);int cost 0;for (char digit : strX.toCharArray()) {if (strY.contains(String.valueOf(digit))) {cost Character.getNumericValue(digit);}}return cost;}public static void main(String[] args) {int n 2021;UnionFind uf new UnionFind(n 1);int[][] dp new int[n 1][n 1];// 构建并查集for (int i 1; i n; i) {for (int j i 1; j n; j) {int cost calculateCost(i, j);dp[i][j] cost;dp[j][i] cost;if (cost 0) {uf.union(i, j);}}}// 合并连通分量int[] set new int[n 1];Arrays.fill(set, -1);for (int i 1; i n; i) {int root uf.find(i);if (set[root] -1) {set[root] i;}}// 计算最小装饰费用int answer 0;for (int i 1; i n; i) {if (set[i] ! -1) {answer dp[1][set[i]];}}System.out.println(answer);}
}
