题目
给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V,E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行,每行包含三个整数u,v, w,表示点u和点v之间存在一条权值为w的边。
输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
数据范围
1
≤
n
≤
1
0
5
1 \le n \le 10^5
1≤n≤105,
1
≤
m
≤
2
∗
1
0
5
1 \le m \le 2*10^5
1≤m≤2∗105,
- 输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
- 输出样例:
6
题解
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/**
* @author akuya
* @create 2023-07-11-17:25
*/
public class Kruskal {
static int N = 200010;
static int n, m;
static int p[] = new int[N];
static Edge_Krus edges[] ;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
init();
edges=new Edge_Krus[m];
for (int i = 0; i <m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int w = scanner.nextInt();
edges[i] = new Edge_Krus(a, b, w);
}
Arrays.sort(edges, new Comparator<Edge_Krus>() {
@Override
public int compare(Edge_Krus o1, Edge_Krus o2) {
return o1.w-o2.w;
}
});
int res=0;
int cnt=0;
for(int i=0;i<m;i++){
int a=edges[i].a;
int b=edges[i].b;
int w=edges[i].w;
a=find(a);b=find(b);
if(a!=b){
union(a,b);
res+=w;
cnt++;
}
}
if(cnt<n-1) System.out.println("impossible");
else System.out.println(res);
}
public static void init() {
for (int i = 1; i <= n; i++) {
p[i] = i;
}
}
public static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void union(int a,int b){
p[a]=b;
}
}
class Edge_Krus{
int a;
int b;
int w;
public Edge_Krus(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
思路
Kruskal算法的思想有两步,如下图
具体原理这里就不详述了,这里只讲方法,通过代码实现后即如图解模板。
Kruskal用于处理稀疏图,时间复杂度与堆优化版prim算法相近,但kruskal算法写起来比堆优化轻松,所以本人倾向于kruskal解决稀疏图。