代码
Java 自带快速排序
import java.util.*;
import java.io.*;
public class Main {
static int N = 100010, NaN = 0x3f3f3f3f, n;
/**
* 自定义数据类型,实现 Comparable 借口,方便 Arrays.sort 排序
*/
static class Edge implements Comparable<Edge> {
int a;
int b;
int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
@Override
public int compareTo(Edge e) {
return w - e.w;
}
}
/**
* 点边关系数组,不能有 null ,会影响排序
*/
static Edge[] es;
/**
* 并查集数组
*/
static int[] p = new int[N];
/**
* 查询某个节点的集合根节点编号
*/
static int find(int i) {
if (p[i] != i) p[i] = find(p[i]);
return p[i];
}
/**
* Kruskal 算法
*/
static int kruskal() {
// 将点边关系数组,从小到大排序
Arrays.sort(es);
// res 最小生成树边权之和,cnt 构成最小生成树的边数之和
int res = 0, cnt = 0;
// 遍历每条边
for (Edge e : es) {
// 查询两点所属集合的根节点编号
int pa = find(e.a);
int pb = find(e.b);
// 如果两点未连通
if (pa != pb) {
// 连通两点
p[pa] = pb;
// 边权值之和,加上当前边的权值
res += e.w;
// 边数 + 1
cnt ++;
}
}
// 遍历完每条边之后,如果生成的最小生成树边数,比总点数 - 1 小,说明有未连通的点,不存在最小生成树
// 否则返回最小生成树的边权之和
return cnt < n - 1 ? NaN : res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
// 初始将所有点默认不连通,分属单独的集合
for (int i = 1; i <= n; i ++) {
p[i] = i;
}
int m = sc.nextInt();
es = new Edge[m];
for (int i = 0; i < m; i ++) {
es[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
int t = kruskal();
System.out.println(t == NaN ? "impossible" : t);
sc.close();
}
}
手写快速排序
import java.util.*;
import java.io.*;
public class Main {
static int N = 100010, NaN = 0x3f3f3f3f, n, m;
/**
* 自定义数据类型,存储点边关系
*/
static class Edge {
int a, b, w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
/**
* 点边关系数组
*/
static Edge[] es;
/**
* 并查集数组
*/
static int[] p = new int[N];
/**
* 查询某个节点的集合根节点编号
*/
static int find(int i) {
if (p[i] != i) p[i] = find(p[i]);
return p[i];
}
/**
* 手写快速排序
*/
static void quickSort(int l, int r) {
if (l >= r) return;
Edge ed = es[l];
int i = l - 1, j = r + 1;
while (i < j) {
do i ++; while (es[i].w < ed.w);
do j --; while (es[j].w > ed.w);
if (i < j) {
Edge t = es[i];
es[i] = es[j];
es[j] = t;
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
/**
* kruskal 算法
*/
static int kruskal() {
// 将点边关系数组,从小到大排序
quickSort(0, m - 1);
// res 最小生成树边权之和,cnt 构成最小生成树的边数之和
int res = 0, cnt = 0;
// 遍历每条边
for (Edge e : es) {
// 查询两点所属集合的根节点编号
int pa = find(e.a), pb = find(e.b);
// 如果两点未连通
if (pa != pb) {
// 连通两点
p[pa] = pb;
// 边权值之和,加上当前边的权值
res += e.w;
// 边数 + 1
cnt ++;
}
}
// 遍历完每条边之后,如果生成的最小生成树边数,比总点数 - 1 小,说明有未连通的点,不存在最小生成树
// 否则返回最小生成树的边权之和
return cnt < n - 1 ? NaN : res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
// 初始将所有点默认不连通,分属单独的集合
for (int i = 1; i <= n; i ++) {
p[i] = i;
}
m = sc.nextInt();
es = new Edge[m];
for (int i = 0; i < m; i ++) {
es[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
int t = kruskal();
System.out.println(t == NaN ? "impossible" : t);
sc.close();
}
}