Problem: BOJ 2887 — Planet Tunnel
Sparse candidate edges for Kruskal
For planets u and v, the tunnel cost is min(|x[u] - x[v]|, |y[u] - y[v]|, |z[u] - z[v]|). Building all N(N - 1) / 2 edges is too expensive when N is large. Instead, sort the planets separately by each coordinate and keep only the edges between consecutive planets in each ordering. This produces at most 3(N - 1) candidates.
Why are these candidates enough? Consider any edge in a minimum spanning tree, and choose a coordinate whose absolute difference equals that edge’s cost; call that difference d. If another planet lies between its endpoints in this coordinate ordering, the endpoints are not consecutive. Along the ordered sequence between them, every consecutive coordinate gap is strictly less than d. The actual tunnel cost of each such consecutive pair is at most its gap, because the tunnel cost is the minimum of the three coordinate differences. Thus those consecutive edges form a path of edges each strictly cheaper than the chosen MST edge. Removing that edge from the tree creates a cut; the path crosses that cut, so one of its cheaper edges can reconnect the two sides. That contradicts minimality. Therefore each MST edge is consecutive in at least one coordinate ordering and is included among the candidates.
For each candidate pair, use its actual tunnel cost (the minimum across all three axes), not necessarily the difference in the axis used to discover the pair. Kruskal’s algorithm sorts these edges and uses a disjoint-set union structure to add an edge only when it joins two components. N = 1 yields no candidates and a total cost of zero. Coordinate differences are computed as long before taking the absolute value, and the accumulated MST cost is also long.
Each of the three coordinate sorts takes O(N log N) time and creates O(N) candidates. Sorting the O(N) candidates and running Kruskal take O(N log N) and O(N α(N)), respectively, so the total time is O(N log N) and space is O(N).
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
static class Planet {
int x;
int y;
int z;
int id;
Planet(int x, int y, int z, int id) {
this.x = x;
this.y = y;
this.z = z;
this.id = id;
}
}
static class Edge implements Comparable<Edge> {
int from;
int to;
long cost;
Edge(int from, int to, long cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge other) {
return Long.compare(cost, other.cost);
}
}
static class DisjointSet {
int[] parent;
int[] rank;
DisjointSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
int find(int value) {
if (parent[value] != value) {
parent[value] = find(parent[value]);
}
return parent[value];
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else {
parent[rootB] = rootA;
rank[rootA]++;
}
return true;
}
}
static long difference(int a, int b) {
return Math.abs((long) a - b);
}
static long tunnelCost(Planet a, Planet b) {
return Math.min(difference(a.x, b.x),
Math.min(difference(a.y, b.y), difference(a.z, b.z)));
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
Planet[] planets = new Planet[n];
for (int i = 0; i < n; i++) {
planets[i] = new Planet(input.nextInt(), input.nextInt(), input.nextInt(), i);
}
List<Edge> candidates = new ArrayList<>(Math.max(0, 3 * (n - 1)));
Planet[] ordered = planets.clone();
for (int axis = 0; axis < 3; axis++) {
final int coordinate = axis;
Arrays.sort(ordered, (a, b) -> Integer.compare(
coordinate(a, coordinate), coordinate(b, coordinate)));
for (int i = 0; i + 1 < n; i++) {
Planet a = ordered[i];
Planet b = ordered[i + 1];
candidates.add(new Edge(a.id, b.id, tunnelCost(a, b)));
}
}
candidates.sort(null);
DisjointSet sets = new DisjointSet(n);
long total = 0;
int used = 0;
for (Edge edge : candidates) {
if (sets.union(edge.from, edge.to)) {
total += edge.cost;
if (++used == n - 1) {
break;
}
}
}
System.out.println(total);
}
static int coordinate(Planet planet, int axis) {
if (axis == 0) return planet.x;
if (axis == 1) return planet.y;
return planet.z;
}
static class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int ptr;
private int len;
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
private int read() throws IOException {
if (ptr == len) {
len = in.read(buffer);
ptr = 0;
if (len == -1) return -1;
}
return buffer[ptr++];
}
}
}