当谈论并查集时，我们可以继续使用上述的动物园比喻来解释它的概念。
我们可以把并查集看作是一个动物园管理系统，帮助你管理动物们的归属关系。
在这个动物园中，每个动物都有一个独特的编号，代表一个独立的元素。一开始，每个动物都是独立的，没有与其他动物建立关系。
-
初始化（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; // 将两个笼子合并，让一个根节点指向另一个根节点
}
}
}首先，我们需要根据输入的桥的信息构建并查集。
对于每座桥，如果它的使用天数超过了指定的天数，我们将这两个小岛合并成同一个集合。如果它的使用天数没有超过指定的天数，说明这座桥可以使用，我们不需要对这两个小岛进行合并。
接下来，我们遍历所有的桥，对于每座桥，我们查找连接的两个小岛是否属于同一个集合。如果不属于同一个集合，说明这两个小岛之间没有其他路径可以到达，居民们会抗议的天数加一。
最后，输出居民们会抗议的天数即可。
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);
}
}第二道题
这道题有两个思路：
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);
}
}