Kruskal算法复盘
作者:
火球大的脸盆
,
2022-08-12 17:55:46
,
所有人可见
,
阅读 214
import java.io.*;
import java.util.*;
class Edge {
int a, b, w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
public class Main {
static final int N = 200010;
static int n, m;
static int u, v, w;
static int[] p = new int[N];
static Edge[] edge = new Edge[N];
static int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
static int Kruskal() {
int res = 0;
int cnt = 0;
Arrays.sort(edge, 0, m, (a, b)->{return a.w - b.w;});
for (int i = 0; i < m; i++) {
Edge e = edge[i];
int a = e.a;
int b = e.b;
int w = e.w;
a = find(a);
b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt++;
}
}
if (cnt < n - 1) return 0x3f3f3f3f;
return res;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first_line = br.readLine().split(" ");
n = Integer.parseInt(first_line[0]);
m = Integer.parseInt(first_line[1]);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++) {
String[] second_line = br.readLine().split(" ");
u = Integer.parseInt(second_line[0]);
v = Integer.parseInt(second_line[1]);
w = Integer.parseInt(second_line[2]);
edge[i] = new Edge(u, v, w);
}
int ans = Kruskal();
if (ans == 0x3f3f3f3f) {
bw.write("impossible\n");
bw.flush();
}
else {
bw.write(ans + "\n");
bw.flush();
}
}
}