Hungarian.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

class Hungarian {

    public static void main(String[] args) {

        long start = System.currentTimeMillis();

        int n = 4096;

        double[][] theCosts = new double[n][n];

        Random random = new Random(2019);

        for (int i = 0; i < n; i++) {
            theCosts[i][i] = random.nextDouble();
        }

        Hungarian hungarian = new Hungarian(theCosts);

        System.out.println(Arrays.deepHashCode(hungarian.execute()));

        long finish = System.currentTimeMillis();
        System.out.println(finish - start);

    }

    int numRows;
    int numCols;

    boolean[][] primes;
    boolean[][] stars;
    boolean[] rowsCovered;
    boolean[] colsCovered;
    double[][] costs;

    Hungarian(double[][] theCosts) {
        costs = theCosts;
        numRows = costs.length;
        numCols = costs[0].length;

        primes = new boolean[numRows][numCols];
        stars = new boolean[numRows][numCols];

        rowsCovered = new boolean[numRows];
        colsCovered = new boolean[numCols];

    }

    int[][] execute() {
        for (int i = 0; i < numRows; i++) {
            double rowMin = Double.MAX_VALUE;
            for (int j = 0; j < numCols; j++) {
                if (costs[i][j] < rowMin) {
                    rowMin = costs[i][j];
                }
            }
            for (int j = 0; j < numCols; j++) {
                costs[i][j] = costs[i][j] - rowMin;
            }
        }

        for (int j = 0; j < numCols; j++) {
            double colMin = Double.MAX_VALUE;
            for (int i = 0; i < numRows; i++) {
                if (costs[i][j] < colMin) {
                    colMin = costs[i][j];
                }
            }
            for (int i = 0; i < numRows; i++) {
                costs[i][j] = costs[i][j] - colMin;
            }
        }

        boolean[] rowStars = new boolean[numRows];
        boolean[] colStars = new boolean[numCols];

        for (int i = 0; i < numRows; i++) {
            rowStars[i] = false;
        }
        for (int j = 0; j < numCols; j++) {
            colStars[j] = false;
        }

        for (int j = 0; j < numCols; j++) {
            for (int i = 0; i < numRows; i++) {
                if (costs[i][j] == 0 && !rowStars[i] && !colStars[j]) {
                    stars[i][j] = true;
                    rowStars[i] = true;
                    colStars[j] = true;
                    break;
                }
            }
        }
        resetCovered();
        coverStarredZeroCols(numRows, numCols, stars, colsCovered);

        while (!allColsCovered(numCols, colsCovered)) {
            int[] primedLocation = primeUncoveredZero();

            if (primedLocation[0] == -1) {
                double minUncovered = Double.MAX_VALUE;
                for (int i = 0; i < numRows; i++) {
                    if (!rowsCovered[i]) {
                        for (int j = 0; j < numCols; j++) {
                            if (!colsCovered[j]) {
                                if (costs[i][j] < minUncovered) {
                                    minUncovered = costs[i][j];
                                }
                            }
                        }
                    }
                }

                for (int i = 0; i < numRows; i++) {
                    if (rowsCovered[i]) {
                        for (int j = 0; j < numCols; j++) {
                            costs[i][j] = costs[i][j] + minUncovered;

                        }
                    }
                }

                for (int j = 0; j < numCols; j++) {
                    if (!colsCovered[j]) {
                        for (int i = 0; i < numRows; i++) {
                            costs[i][j] = costs[i][j] - minUncovered;
                        }
                    }
                }
                primedLocation = primeUncoveredZero();
            }

            int primedRow = primedLocation[0];
            int starCol = findStarColInRow(primedRow, numCols, stars);
            if (starCol != -1) {
                rowsCovered[primedRow] = true;
                colsCovered[starCol] = false;
            } else {
                ArrayList<int[]> primeLocations = new ArrayList<int[]>(numRows + numCols);
                ArrayList<int[]> starLocations = new ArrayList<int[]>(numRows + numCols);
                primeLocations.add(primedLocation);

                int currentRow = primedLocation[0];
                int currentCol = primedLocation[1];
                while (true) {
                    int starRow = findStarRowInCol(currentCol, numRows, stars);
                    if (starRow == -1) {
                        break;
                    }
                    int[] starLocation = new int[] { starRow, currentCol };
                    starLocations.add(starLocation);
                    currentRow = starRow;

                    int primeCol = findPrimeColInRow(currentRow, numCols, primes);
                    int[] primeLocation = new int[] { currentRow, primeCol };
                    primeLocations.add(primeLocation);
                    currentCol = primeCol;
                }

                for (int k = 0; k < starLocations.size(); k++) {
                    int[] starLocation = starLocations.get(k);
                    int row = starLocation[0];
                    int col = starLocation[1];
                    stars[row][col] = false;
                }
                for (int k = 0; k < primeLocations.size(); k++) {
                    int[] location1 = primeLocations.get(k);
                    int row = location1[0];
                    int col = location1[1];
                    stars[row][col] = true;
                }
                resetCovered();
                for (int i = 0; i < numRows; i++) {
                    for (int j = 0; j < numCols; j++) {
                        primes[i][j] = false;
                    }
                }
                coverStarredZeroCols(numRows, numCols, stars, colsCovered);
            }
        }

        return starsToAssignments();

    }

    int[][] starsToAssignments() {
        int[][] toRet = new int[numCols][];
        for (int j = 0; j < numCols; j++) {
            toRet[j] = new int[] { findStarRowInCol(j, numRows, stars), j }; // O(n)
        }
        return toRet;
    }

    void resetCovered() {
        for (int i = 0; i < numRows; i++) {
            rowsCovered[i] = false;
        }
        for (int j = 0; j < numCols; j++) {
            colsCovered[j] = false;
        }
    }

    int[] primeUncoveredZero() {
        int[] location = new int[2];

        for (int i = 0; i < numRows; i++) {
            if (!rowsCovered[i]) {
                for (int j = 0; j < numCols; j++) {
                    if (!colsCovered[j]) {
                        if (costs[i][j] == 0) {
                            primes[i][j] = true;
                            location[0] = i;
                            location[1] = j;
                            return location;
                        }
                    }
                }
            }
        }

        location[0] = -1;
        location[1] = -1;
        return location;
    }

    int findPrimeColInRow(int theRow, int numCols, boolean[][] primes) {
        for (int j = 0; j < numCols; j++) {
            if (primes[theRow][j]) {
                return j;
            }
        }
        return -1;
    }

    int findStarRowInCol(int theCol, int numRows, boolean[][] stars) {
        for (int i = 0; i < numRows; i++) {
            if (stars[i][theCol]) {
                return i;
            }
        }
        return -1;
    }

    int findStarColInRow(int theRow, int numCols, boolean[][] stars) {
        for (int j = 0; j < numCols; j++) {
            if (stars[theRow][j]) {
                return j;
            }
        }
        return -1;
    }

    boolean allColsCovered(int numCols, boolean[] colsCovered) {
        for (int j = 0; j < numCols; j++) {
            if (!colsCovered[j]) {
                return false;
            }
        }
        return true;
    }

    void coverStarredZeroCols(int numRows, int numCols, boolean[][] stars, boolean[] colsCovered) {
        for (int j = 0; j < numCols; j++) {
            colsCovered[j] = false;
            for (int i = 0; i < numRows; i++) {
                if (stars[i][j]) {
                    colsCovered[j] = true;
                    break;
                }
            }
        }
    }

}