Download

import org.jgrapht.Graph; import org.jgrapht.alg.matching.KuhnMunkresMinimalWeightBipartitePerfectMatching; import org.jgrapht.graph.DefaultWeightedEdge; import org.jgrapht.graph.SimpleWeightedGraph;

import java.util.Scanner;

public class HungarianAssignmentSolver {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.print("Enter the number of rows: ");
    int rows = scanner.nextInt();

    System.out.print("Enter the number of columns: ");
    int cols = scanner.nextInt();

    int[][] costMatrix = new int[rows][cols];

    System.out.println("Enter the matrix elements:");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            costMatrix[i][j] = scanner.nextInt();
        }
    }

    int[][] graph = convertToGraph(costMatrix);
    int optimalValue = findOptimalValue(graph);

    System.out.println("Optimal Value = " + optimalValue);
}

private static int[][] convertToGraph(int[][] costMatrix) {
    int rows = costMatrix.length;
    int cols = costMatrix[0].length;
    int[][] graph = new int[rows + cols][rows + cols];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            graph[i][j + rows] = costMatrix[i][j];
            graph[j + rows][i] = costMatrix[i][j];
        }
    }
    return graph;
}

private static int findOptimalValue(int[][] graph) {
    Graph<Integer, DefaultWeightedEdge> weightedGraph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

    for (int i = 0; i < graph.length; i++) {
        weightedGraph.addVertex(i);
    }

    for (int i = 0; i < graph.length; i++) {
        for (int j = 0; j < graph[i].length; j++) {
            if (i != j) {
                DefaultWeightedEdge edge = weightedGraph.addEdge(i, j);
                if (edge != null) {
                    weightedGraph.setEdgeWeight(edge, graph[i][j]);
                }
            }
        }
    }

    KuhnMunkresMinimalWeightBipartitePerfectMatching<Integer, DefaultWeightedEdge> km =
            new KuhnMunkresMinimalWeightBipartitePerfectMatching<>(weightedGraph);
    km.getMatching();

    int optimalValue = 0;
    for (DefaultWeightedEdge edge : weightedGraph.edgeSet()) {
        optimalValue += weightedGraph.getEdgeWeight(edge);
    }

    return optimalValue / 2; // Since each edge is counted twice in the matching
}

}