D-Dimensional MST

You are given $N$ points in $D$-dimensional space. The point has $D$ coordinates - $xi,1,xi,2,…,xi,D$.

Consider a weighted undirected complete graph with these $N$ points as its vertices. Weight of the edge between points $i$ and $j$ is $∣xi,1−xj,1∣+∣xi,2−xj,2∣+…+∣xi,D−xj,D∣$.

Find the weight of the maximum spanning tree of this graph.

Input:

• The first line contains two integers $N,D$.

• The $i$-th of the next $N$ lines contains a description of the $ii$-th point. It has D$DD$ integers: $xi,1,xi,2,…,xi,D$.

Output: Output a single line which contains a single integer - the Maximum Spanning Tree Weight

Constraints

• $1≤D≤51≤D≤5$

• $1≤N≤200 0001≤N≤200000$

• $0≤xi,j≤100 0000≤xi,j​≤100000$

Subtasks

• 10 points, $N≤5000N≤5000$

• 90 points, $N≤200 000N≤200000$

Sample 1:

Input:

2 2  
1 1  
2 2

Output

2

Answer

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(), d = s.nextInt();
        int[][] arr = new int[n][d];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++)
                arr[i][j] = s.nextInt();
        }
        // Graph creation
        int[][] graph = new int[n][n];
        int[] key = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int wt = 0;
                for (int k = 0; k < d; k++)
                    wt += Math.abs(arr[i][k] - arr[j][k]);
                graph[i][j] = wt;
            }
            if (i != 0)
                key[i] = Integer.MIN_VALUE;
        }
        Set<Integer> set = new HashSet<>();
        long ans = 0;
        while (set.size() != n) {
            // Find the vertex with max key value & not in mst
            // AKA find the min wt edge such that 1 vertex is in mst and the other is not
            int max = -1;
            int vertex = -1;
            for (int i = 0; i < n; i++) {
                if (!set.contains(i) && key[i] > max) {
                    max = key[i];
                    vertex = i;
                }
            }
            set.add(vertex);
            ans += max;
            for (int i = 0; i < n; i++) {
                if (!set.contains(i)) {
                    key[i] = Math.max(key[i], graph[vertex][i]);
                }
            }
        }
        System.out.println(ans);
    }
}