standard input 5 20 1 2 1 5 2 1 2 1 1 5 2 1 2 1 1 5 2 1 5 4 2 2 4 3 2 1 3 4 1 3 2 4 3 1 5 4 4 3 5 1 2 5 1 2 5 5 1 5 1 2 1 2 3 2 1 4 3 3 5 4 12
时间: 2024-01-04 13:04:51 浏览: 24
```java
import java.util.*;
class Edge {
int u, v, weight;
public Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
}
class UnionFind {
int[] parent;
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 (x != parent[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 class MinimumSpanningTreeCount {
public static long countMSTs(int n, Edge[] edges) {
Arrays.sort(edges, Comparator.comparingInt(e -> e.weight));
UnionFind uf = new UnionFind(n);
long count = 1;
for (Edge edge : edges) {
int u = edge.u;
int v = edge.v;
if (uf.find(u) != uf.find(v)) {
uf.union(u, v);
count *= 2;
}
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
Edge[] edges = new Edge[m];
for (int i = 0; i < m; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int weight = scanner.nextInt();
edges[i] = new Edge(u, v, weight);
}
long count = countMSTs(n, edges);
System.out.println("Different methods of choosing edges: " + count);
}
}
```
这段代码可以读取标准输入,并使用Kruskal算法来计算无向连通图的最小生成树边集合数量。它首先读取输入的顶点个数n和边的个数m,然后依次读取每条边的起点、终点和权值。最后,输出的结果是不同选择边的方法数量。
您可以将输入数据按照要求输入,然后运行代码,即可得到结果。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)