特定算法：KM

校园自行车分配 II

KM算法的例子：
https://blog.csdn.net/qq_37943488/article/details/78586048
上面这个例子是二分最大全匹配的例子，即男女配对的例子，实现代码如下：

public class KM {

    private int[][] weight; // 二分图两边顶点之间的权重:女生对每个男生的好感度

    private int girlCount; // 女生数量
    private int boyCount; // 男生数量
    private int[] girlValues; // 女生的期望值
    private int[] boyValues; // 男生的期望值
    private int[] matched; // 记录每个男生已经匹配到的女生, -1代表尚未匹配到任何女生

    private boolean[] girlVisit; // 记录每一轮匹配过的女生
    private boolean[] boyVisit; // 记录每一轮匹配过的男生
    private int[] lack; // 记录每一轮的男生如果能被女生倾心至少还需要增加多少value

    public KM(int[][] weight) throws Exception {
        this.weight = weight;
        init();
    }

    public void init() throws Exception {
        girlCount = weight.length;
        boyCount = weight[0].length;
        if (girlCount > boyCount) {
            throw new Exception("girlCount should less or equals than boyCount");
        }

        // 每个女生的期望值初始化为与她相连的男生的最大的好感度
        girlValues = new int[girlCount];
        for (int i = 0; i < girlCount; i++) {
            girlValues[i] = weight[i][0];
            for (int j = 1; j < boyCount; j++) {
                girlValues[i] = Math.max(girlValues[i], weight[i][j]);
            }
        }

        // 每个男生的期望值初始化为0
        boyValues = new int[boyCount];

        // 男生匹配到的女生初始化为-1, 代表男生都还没每有匹配到女生
        matched = new int[boyCount];
        for (int i = 0; i < boyCount; i++) {
            matched[i] = -1;
        }

        // 每一轮之前都需要初始化
        girlVisit = new boolean[girlCount];
        boyVisit = new boolean[boyCount];
        lack = new int[boyCount];
    }

    // 为女生匹配对象, 成功返回true, 失败返回false
    public boolean dfs(int girl) {
        girlVisit[girl] = true;
        for (int boy = 0; boy < boyCount; boy++) {
            if (boyVisit[boy]) {
                continue;
            }
            int gap = girlValues[girl] + boyValues[boy] - weight[girl][boy];
            if (gap == 0) {
                boyVisit[boy] = true;
                if (matched[boy] == -1 || dfs(matched[boy])) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
                    matched[boy] = girl;
                    return true;
                }
            } else {
                lack[boy] = Math.min(lack[boy], gap);
            }
        }
        return false;
    }

    public int getMaxMatchWeight() {
        for (int girl = 0; girl < girlCount; girl++) {
            initLack();
            while (true) {
                initBoyVisit();
                initGirlVisit();
                if (dfs(girl)) {
                    break; // 找到归宿则退出
                }

                // 找不到归宿, 则调整期望值:
                // 所有访问过的女生需要降低期望值, 降低多少取决于这一轮未被访问的男生中最小的lack值
                int down = Integer.MAX_VALUE;
                for (int boy = 0; boy < boyCount; boy++) {
                    if (!boyVisit[boy]) {
                        down = Math.min(down, lack[boy]);
                    }
                }
                for (int theGirl = 0; theGirl < girlCount; theGirl++) {
                    if (girlVisit[theGirl]) {
                        girlValues[theGirl] -= down;
                    }
                }

                // 所有被访问过的男生的期望值可以提升, 未被访问过的男生的lack值可以减小
                for (int theBoy = 0; theBoy < boyCount; theBoy++) {
                    if (boyVisit[theBoy]) {
                        boyValues[theBoy] += down;
                    } else {
                        lack[theBoy] -= down;
                    }
                }
            }
        }
        // 所有女生都匹配到男生, 返回匹配的weight之和即可
        int totalWeight = 0;
        for (int boy = 0; boy < boyCount; boy++) {
            if (matched[boy] > -1) {
                totalWeight += weight[matched[boy]][boy];
            }
        }
        return totalWeight;
    }

    public void initGirlVisit() {
        for (int i = 0; i < girlCount; i++) {
            girlVisit[i] = false;
        }
    }

    public void initBoyVisit() {
        for (int i = 0; i < boyCount; i++) {
            boyVisit[i] = false;
        }
    }

    public void initLack() {
        for (int i = 0; i < boyCount; i++) {
            lack[i] = Integer.MAX_VALUE;
        }
    }

    public static void main(String[] args) {
        int[][] weight = {{3, 2, 3, 4}, {2, 2, 4, 6}, {0, 0, 3, 4}};
        try {
            KM km = new KM(weight);
            int maxWeight = km.getMaxMatchWeight();
            System.out.println(maxWeight);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

将上面的例子稍微更改，即可改为二分最小权的求解算法，可应用与本题的求解：

public class Solution {

    public int assignBikes(int[][] workers, int[][] bikes) {
        int m = workers.length;
        int n = bikes.length;
        int[][] weight = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                weight[i][j] = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
            }
        }
        setWeight(weight);
        return getMinMatchWeight();
    }

    private int[][] weight; // 二分图两边顶点之间的权重:工人与自行车之间的曼哈顿距离

    private int workerCount;
    private int bikeCount;
    private int[] workerValues;
    private int[] bikeValues;

    private int[] matched; // 记录每辆自行车已经匹配的工人

    private boolean[] workerVisit; // 记录每一轮匹配过的worker
    private boolean[] bikeVisit; // 记录每一轮匹配过的bike
    private int[] lack; // 记录每一轮的bike如果能被工人选中至少还需要减少多少距离

    public void setWeight(int[][] weight) {
        this.weight = weight;
        init();
    }

    public void init() {
        workerCount = weight.length;
        bikeCount = weight[0].length;

        // 每个worker的期望值初始化为与他距离最近的车的距离
        workerValues = new int[workerCount];
        for (int i = 0; i < workerCount; i++) {
            workerValues[i] = weight[i][0];
            for (int j = 1; j < bikeCount; j++) {
                workerValues[i] = Math.min(workerValues[i], weight[i][j]); // 改动:期望值是最小距离
            }
        }

        // 每个bike的期望值初始化为0
        bikeValues = new int[bikeCount];

        // bike匹配到的工人初始化为-1, 代表bike都还没每有匹配到工人
        matched = new int[bikeCount];
        for (int i = 0; i < bikeCount; i++) {
            matched[i] = -1;
        }

        // 每一轮之前都需要初始化
        workerVisit = new boolean[workerCount];
        bikeVisit = new boolean[bikeCount];
        lack = new int[bikeCount];
    }

    // 为worker匹配自行车, 成功返回true, 失败返回false
    public boolean dfs(int worker) {
        workerVisit[worker] = true;
        for (int bike = 0; bike < bikeCount; bike++) {
            if (bikeVisit[bike]) {
                continue;
            }
            int gap = weight[worker][bike] - (workerValues[worker] + bikeValues[bike]); // 改动:保证gap为正数
            if (gap == 0) {
                bikeVisit[bike] = true;
                if (matched[bike] == -1 || dfs(matched[bike])) { // 找到一个没有匹配的bike 或者该bike的worker可以找到其他worker
                    matched[bike] = worker;
                    return true;
                }
            } else {
                lack[bike] = Math.min(lack[bike], gap);
            }
        }
        return false;
    }

    public int getMinMatchWeight() {
        for (int worker = 0; worker < workerCount; worker++) {
            initLack();
            while (true) {
                initBikeVisit();
                initWorkerVisit();
                if (dfs(worker)) {
                    break; // 找到biker则退出
                }

                // 找不到bike, 则调整距离:
                // 所有访问过的worker需要增加距离值, 增加多少取决于这一轮未被访问的bike中最小的lack值
                int down = Integer.MAX_VALUE;
                for (int bike = 0; bike < bikeCount; bike++) {
                    if (!bikeVisit[bike]) {
                        down = Math.min(down, lack[bike]);
                    }
                }
                for (int theWorker = 0; theWorker < workerCount; theWorker++) {
                    if (workerVisit[theWorker]) {
                        workerValues[theWorker] += down; // 改动:降低期望值，即增大可容忍的距离
                    }
                }

                // 所有被访问过的bike的距离值可以下降, 未被访问过的bike的lack值可以减小
                for (int theBoy = 0; theBoy < bikeCount; theBoy++) {
                    if (bikeVisit[theBoy]) {
                        bikeValues[theBoy] -= down; // 改动:增加bike的期望值，即bike减小自身的值, 距离越近越容易被选择
                    } else {
                        lack[theBoy] -= down;
                    }
                }
            }
        }
        // 所有worker都匹配到bike, 返回匹配的weight之和即可
        int totalWeight = 0;
        for (int bike = 0; bike < bikeCount; bike++) {
            if (matched[bike] > -1) {
                totalWeight += weight[matched[bike]][bike];
            }
        }
        return totalWeight;
    }

    public void initWorkerVisit() {
        for (int i = 0; i < workerCount; i++) {
            workerVisit[i] = false;
        }
    }

    public void initBikeVisit() {
        for (int i = 0; i < bikeCount; i++) {
            bikeVisit[i] = false;
        }
    }

    public void initLack() {
        for (int i = 0; i < bikeCount; i++) {
            lack[i] = Integer.MAX_VALUE;
        }
    }
}