匈牙利算法java版（超级简单好用）

package cn.sgnxotsmicf.XYL;

import java.util.ArrayList;
import java.util.Scanner;


public class Data{
    public static int [] ZeroRow; //0的行位置数组
    public static int [] ZeroColumn; //0的列位置数组
    public static int [] ActiveZeroRow; //有效0（画圈0）的行位置数组
    public static int [] ActiveZeroColumn; //有效0（画圈0）的列位置数组
    public static int [] NegativeZeroRow;  // 非有效0（画线0）~
    public static int [] NegativeZeroColumn; //~
    public static ArrayListOKZero_RowLine; //对勾行
    public static ArrayListOKZero_ColumnLine; //DrawZero_ColumnLine 对勾列，也等于划线列
    public static ArrayListDrawZero_RowLine; //划线行
    public static ArrayListLI_RANGRow;  //礼让行
    public static ArrayListLI_RANGColumn; //礼让列
    public static int [][] A;
    public static int dim; //A的阶数
    public static int ZeroNumber; //有效0个数
    static {
        System.out.println("匈牙利算法！！！");
    }

    public static int[][] input(){
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入矩阵的阶数:");
        dim = sc.nextInt();
        A = new int[dim][dim];
        System.out.println("输入矩阵:");
        for (int i = 0; i < dim; i++) {
            System.out.println("请输入第"+(i+1)+"行元素:");
            for (int j = 0; j < dim; j++) {
                A[i][j] = sc.nextInt();
            }
        }
        //sb设计，但不想改了，不够用自己扩充，或者改成集合
        ZeroRow = new int[2*dim+2];
        ZeroColumn = new int[2*dim+2];
        ActiveZeroRow = new int[2*dim+2];
        ActiveZeroColumn = new int[2*dim+2];
        NegativeZeroRow = new int[2*dim+2];
        NegativeZeroColumn = new int[2*dim+2];
        ZeroNumber = 0;
        return copyMatrix(A);
    }
    
    public static void printMatrix(int [][] A){
        for (int i = 0; i < dim; i++) {
            for (int j = 0; j < dim; j++) {
                System.out.print(A[i][j]+(j == dim-1?" ":","));
            }
            System.out.println();
        }
    }
    
    public static int[][] copyMatrix(int[][] A){
        int [][]B = new int[dim][dim];
        for (int i = 0; i < dim; i++) {
            System.arraycopy(A[i], 0, B[i], 0, dim);
        }
        return B;
    }
}

package cn.sgnxotsmicf.XYL;

import java.util.*;


public class XYL_Algorithm extends Data{

    public static void main(String[] args) {

        int[][] B = input();//导入矩阵
        int number = 1;
        while (true) {
            System.out.println("==============第"+number+"次迭代============");
            initZero(); //初始化位置
            if (number==1){
                ReduceZero(); //减最小值
            }
            SearchZero(); //寻找零元
            ObtainValuableZero();//获得有效0
            System.out.println("有效0个数:"+ZeroNumber);
             //结束循环判断
            if (JudgeBreak()){
                System.out.println("得到最优解");
                int sum = CalculateValueNumber(B);
                System.out.println("最优值为:"+sum);
                break;
            }
            OKLine();//画对勾
            drawLine();//画线
            int min = ReduceMin();//减最小
            AddMin(min,number);//加最小
            number++;
        }

    }

    private static int CalculateValueNumber(int[][] B) {
        int sum = 0;
        for (int i = 0; i < 2 * dim; i++) {
            for (int j = 0; j < dim; j++) {
                if (ActiveZeroRow[i]==j){
                  sum +=  B[ActiveZeroRow[i]][ActiveZeroColumn[i]];
                    break;
                }
            }
        }
        return sum;
    }

    private static void AddMin(int min,int number) {
        for (int i = 0; i < dim; i++) {
            for (Integer value : DrawZero_RowLine) {
                if (i == value) {
                    for (int j = 0; j < dim; j++) {
                        for (Integer integer : OKZero_ColumnLine) {
                            if (j == integer) {
                                A[i][j] += min;
                            }
                        }
                    }
                    break;
                }
            }
        }
        System.out.println("第"+number+"次迭代最后的A:");
        printMatrix(A);
    }

    private static int ReduceMin() {
        ArrayList valuableNumber = new ArrayList<>();
        //以A为基准
            for (int j = 0; j < dim; j++) {
                int index = 0;
                for (Integer value : OKZero_ColumnLine) {
                    if (j != value) {
                        index++;
                    }
                }
                if (index == OKZero_ColumnLine.size()){
                    for (int i = 0; i < dim; i++) {
                        int number = 0;
                        for (Integer integer : DrawZero_RowLine) {
                            if (i != integer) {
                                number++;
                            }
                        }
                        if (number ==DrawZero_RowLine.size()){
                            valuableNumber.add(A[i][j]);
                        }
                    }
                }
            }
        System.out.println("没有被划线的元素:"+valuableNumber);

            //找最小值
            int min = valuableNumber.get(0);
        for (Integer item : valuableNumber) {
            min = Math.min(min, item);
        }
        System.out.println("没有被划线元素中的最小值:"+min);
        //减最小值
        for (int j = 0; j < dim; j++) {
            int index = 0;
            for (Integer value : OKZero_ColumnLine) {
                if (j != value) {
                    index++;
                }
            }
            if (index == OKZero_ColumnLine.size()){
                for (int i = 0; i < dim; i++) {
                    int number = 0;
                    for (Integer integer : DrawZero_RowLine) {
                        if (i != integer) {
                            number++;
                        }
                    }
                    if (number ==DrawZero_RowLine.size()){
                        A[i][j] -= min;
                    }
                }
            }
        }
        return min;
    }

    private static void drawLine() {
        int[] calibrate = creat_Calibrate();
        for (int i = 0; i < calibrate.length; i++) {
            int number = 0;
            for (Integer integer : OKZero_RowLine) {
                if (calibrate[i] == integer) {
                    number++;
                }
            }
            if (number==0){
                DrawZero_RowLine.add(i);
            }
        }
        //测验
        System.out.println("画线行:"+DrawZero_RowLine);
        System.out.println("画线列:"+OKZero_ColumnLine);
    }

    private static void OKLine() {
        //校准数组
        int[] calibrate = creat_Calibrate();
        System.out.println("校准数组:"+Arrays.toString(calibrate));
        //对没有圈的行打勾
        for (int j = 0; j < calibrate.length; j++) {
            int number = 0;
            for (int i = 0; i < ActiveZeroRow.length; i++) { //int j = 0; j < calibrate.length; j++
                if (calibrate[j]==ActiveZeroRow[i]){
                    number++;
                }
                if (number == 0 && i == ActiveZeroRow.length-1){
                    //没有圈的行找到 --j--j行
                    OKZero_RowLine.add(j); //行对勾初步位置
                    for (int k = 0; k < NegativeZeroRow.length; k++) {//1.
                        if (NegativeZeroRow[k] == j){
                            OKZero_ColumnLine.add(NegativeZeroColumn[k]); //NegativeZeroColumn[k]列找到
                            int key = NegativeZeroColumn[k];
                            NegativeZeroRow[k] = -1;
                            NegativeZeroColumn[k] = -1;
                            for (int m = 0; m < ActiveZeroColumn.length; m++) {//2.
                                if (key == ActiveZeroColumn[m]){ // ActiveZeroRow(m)行找到
                                   // ActiveZeroRow(m)
                                    OKZero_RowLine.add(ActiveZeroRow[m]);//列对勾初步位置
                                    ActiveZeroRow[m] = -1;
                                    ActiveZeroColumn[m] = -1;
                                }
                            }
                        }
                    }
                }
            }
        }
        while (true) {
            int number = 0;
            for (int i = 0; i < OKZero_RowLine.size(); i++) {
                for (int j = 0; j < NegativeZeroRow.length; j++) {
                    if (NegativeZeroRow[j] == OKZero_RowLine.get(i)){ //行中仍然还有消极零元
                        OKZero_ColumnLine.add(NegativeZeroColumn[j]);//NegativeZeroColumn[j]列找到
                        int column = NegativeZeroColumn[j];
                        NegativeZeroRow[j] = -1;
                        NegativeZeroColumn[j] = -1;
                        for (int k = 0; k < ActiveZeroColumn.length; k++) {
                            if (ActiveZeroColumn[k]==column){ //ActiveZeroColumn[k]行找到
                                OKZero_RowLine.add(ActiveZeroRow[k]);
                                ActiveZeroRow[k] = -1;
                                ActiveZeroColumn[k] = -1;
                            }
                        }
                        number++;
                    }
                }
            }
            if (number == 0){
                break;
            }
        }

        System.out.println("打√行:"+OKZero_RowLine);
        System.out.println("打√列:"+OKZero_ColumnLine);
    }

    private static int[] creat_Calibrate() {
        int[] calibrate = new int[dim];
        int number = 0;
        int index = 0;
        for (int i = 0; i < dim; i++) {
            calibrate[index] = number;
            number++;
            index++;
        }
        return calibrate;
    }


    private static void ObtainValuableZero() {
        //找单行
        int YetSucceedSign = 0;
        int index = 0; //行索引
        int index2 = 0;//列索引
        do {
            for (int i = 0; i < ZeroRow.length; i++) {
                int number = 0;
                for (int k : ZeroRow) {
                    if (ZeroRow[i] == k) {
                        number++;
                    }
                }
                if (number == 1 && ZeroRow[i] != -1) { //加了个-1限制
                    ActiveZeroRow[index] = ZeroRow[i];
                    ActiveZeroColumn[index] = ZeroColumn[i];
                    for (int j = 0; j < ZeroColumn.length; j++) {
                        if (ZeroColumn[j] == ZeroColumn[i] && j != i) {//ZeroColumn[i]
                            NegativeZeroRow[index2] = ZeroRow[j];
                            NegativeZeroColumn[index2] = ZeroColumn[j];
                            ZeroRow[j] = -1;
                            ZeroColumn[j] = -1;
                            ZeroNumber--;
                            index2++;
                        }
                    }
                    ZeroRow[i] = -1;
                    ZeroColumn[i] = -1;
                    index++;
                    i = 0;
                } else {
                    YetSucceedSign++;
                }
            }
            //找单列
            for (int i = 0; i < ZeroColumn.length; i++) {
                int number = 0;
                for (int k : ZeroColumn) {
                    if (ZeroColumn[i] == k) {
                        number++;
                    }
                }
                if (number == 1 && ZeroColumn[i] != -1) {
                    ActiveZeroRow[index] = ZeroRow[i];
                    ActiveZeroColumn[index] = ZeroColumn[i];
                    for (int j = 0; j < ZeroRow.length; j++) {
                        if (ZeroRow[i] == ZeroRow[j] && i != j) {
                            NegativeZeroRow[index2] = ZeroRow[j];
                            NegativeZeroColumn[index2] = ZeroColumn[j];
                            ZeroRow[j] = -1;
                            ZeroColumn[j] = -1;
                            ZeroNumber--;
                            index2++;
                        }
                    }
                    ZeroRow[i] = -1;
                    ZeroColumn[i] = -1;
                    index++;
                    i = 0;
                } else {
                    YetSucceedSign++;
                }
            }

            if (YetSucceedSign == (ZeroRow.length + ZeroColumn.length)) {
                Map map = new HashMap<>();//开始礼让
                for (int i = 0; i < dim; i++) {
                    int min = 0;
                    for (int j = 0; j < ZeroColumn.length; j++) {
                        if (ZeroColumn[j] != -1 && ZeroColumn[j] == i) {
                            //LI_RANGRow.add(ZeroRow[i]);
                            assert LI_RANGColumn != null;
                            LI_RANGColumn.add(ZeroColumn[j]);
                        } else if (j == ZeroColumn.length - 1 && LI_RANGColumn != null && LI_RANGColumn.size() > 0) {
                            for (int k = 0; k < LI_RANGColumn.size(); k++) {
                                int tempt = 1;
                                for (int m = 0; m < ZeroRow.length; m++) {
                                    if (ZeroRow[m] == LI_RANGColumn.get(k)) {
                                        map.put(LI_RANGColumn.get(k), tempt);
                                        tempt++;
                                    } else if (k == 0 && m == ZeroRow.length - 1) {
                                        min = map.get(k);
                                    }
                                }
                                min = Math.min(min, map.get(i));//找到最小列
                            }
                        }
                    }
                    //
                    for (int j = 0; j < ZeroRow.length; j++) {
                        if (ZeroRow[j] == i && ZeroColumn[j] == min) {
                            ActiveZeroRow[index] = ZeroRow[j];
                            ActiveZeroColumn[index] = ZeroColumn[j];
                            ZeroRow[j] = -1;
                            ZeroColumn[j] = -1;
                            index++;
                        } else if (ZeroRow[j] == i) {
                            NegativeZeroRow[index2] = ZeroRow[j];
                            NegativeZeroColumn[index2] = ZeroColumn[j];
                            ZeroRow[j] = -1;
                            ZeroColumn[j] = -1;
                            ZeroNumber--;
                            index2++;
                        }
                    }
                    for (int k = 0; k < ZeroColumn.length; k++) {
                        if (ZeroColumn[k] == min && ZeroRow[k] != i && ZeroRow[k] != -1) {
                            NegativeZeroRow[index2] = ZeroRow[k];
                            NegativeZeroColumn[index2] = ZeroColumn[k];
                            ZeroRow[k] = -1;
                            ZeroColumn[k] = -1;
                            ZeroNumber--;
                            index2++;
                        }
                    }
                    if (LI_RANGColumn != null && LI_RANGColumn.size() > 0) {
                        LI_RANGColumn.clear();
                        break;
                    }
                }
            }
        } while (YetSucceedSign == (ZeroRow.length + ZeroColumn.length));
        System.out.println("有效零元位置:");
        System.out.println(Arrays.toString(ActiveZeroRow));
        System.out.println(Arrays.toString(ActiveZeroColumn));
        System.out.println("非有效零元位置:");
        System.out.println(Arrays.toString(NegativeZeroRow));
        System.out.println(Arrays.toString(NegativeZeroColumn));
    }


    private static boolean JudgeBreak() {
        return ZeroNumber == dim;
    }

    private static void initZero() {
        Arrays.fill(ZeroRow, -1);
        Arrays.fill(ZeroColumn, -1);
        Arrays.fill(ActiveZeroRow, -1);
        Arrays.fill(ActiveZeroColumn, -1);
        Arrays.fill(NegativeZeroRow, -1);
        Arrays.fill(NegativeZeroColumn, -1);
        OKZero_RowLine = new ArrayList<>();
        OKZero_ColumnLine = new ArrayList<>();
        DrawZero_RowLine = new ArrayList<>();
        LI_RANGRow = new ArrayList<>();
        LI_RANGColumn = new ArrayList<>();
        ZeroNumber = 0;
    }

    private static void SearchZero() {
        int row = 0;
        int column = 0;
        for (int i = 0; i < dim; i++) {
            for (int j = 0; j < dim; j++) {
                if (A[i][j]==0){
                    ZeroRow[row] = i;
                    ZeroColumn[column] = j;
                    ZeroNumber++;
                    row++;
                    column++;
                }
            }
        }
        System.out.println("零元位置:");
        System.out.println(Arrays.toString(ZeroRow));
        System.out.println(Arrays.toString(ZeroColumn));
    }

    private static void ReduceZero() {
        //行减0
        for (int i = 0; i < dim; i++) {
            double min = A[i][0];
            for (int j = 0; j < dim; j++) {
                min = Math.min(min,A[i][j]);
                if (min != 0 && j == dim-1){
                    for (int k = 0; k < dim; k++) {
                        A[i][k] -= min;
                    }
                }
            }
        }
        System.out.println("A行减0:");
        printMatrix(A);
        //列减0
        for (int j = 0; j < dim; j++) {
            double min = A[0][j];
            for (int i = 0; i < dim; i++) {
                min = Math.min(min,A[i][j]);
                if (min != 0 && i == dim-1){
                    for (int k = 0; k < dim; k++) {
                        A[k][j] -= min;
                    }
                }
            }
        }
        //验证
        System.out.println("A列减0:");
        printMatrix(A);
    }
}