匈牙利算法（Hungarian Algorithm）是一种组合优化算法，用于在多项式时间内解决指派问题（Assignment Problem）。它的核心思想是在二分图中不断寻找“增广路径”来优化匹配，最终找到总成本最小（或总收益最大）的最优指派方案。

数学模型（指派问题）

• 决策变量：定义二元决策变量 \( x_{ij} \) $$x_{ij} = \begin{cases} 1, & \text{如果第 } i \text{ 个人分配给第 } j \text{ 个任务} \\ 0, & \text{否则} \end{cases}$$
• 目标函数： 我们的目标是最大化总成本指派问题，目标函数可以写为： $$\min Z = \sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij}$$
• 约束条件：
• 每个人只能分配给一个任务： 每个 \( i \) 只能选择一个 \( j \)，即： $$\sum_{j=1}^n x_{ij} = 1, \quad \forall i = 1, 2, \dots, n$$
• 每个任务只能被一个人分配： 每个任务 \( j \) 只能分配给一个人 \( i \)，即： $$\sum_{i=1}^n x_{ij} = 1, \quad \forall j = 1, 2, \dots, n$$
• 二进制变量约束： 每个 \( x_{ij} \) 都是二进制变量，表示任务是否被分配： $$x_{ij} \in \{0, 1\}, \quad \forall i, j$$
• 数学模型 $$\min \sum_{i \in W} \sum_{j \in J} x_{ij}c_{ij}$$ $$\text{s.t.}$$ $$\sum_{j \in J} x_{ij} = 1, \quad \forall i \in \{1, 2, \dots, n\}$$ $$\sum_{i \in W} x_{ij} = 1, \quad \forall j \in \{1, 2, \dots, n\}$$ $$x_{ij} \in \{0, 1\}, \quad \forall i \in \{1, 2, \dots, n\}, \forall j \in \{1, 2, \dots, n\}$$

匈牙利算法

核心概念：图论视角

理解匈牙利算法，首先需要了解其背后的几个关键图论概念：

• 二分图 (Bipartite Graph)：图中的顶点可以分成两个互不相交的集合U和V，且所有的边都连接着U中的一个顶点和V中的一个顶点。在指派问题中，这两个集合可以理解为工人和任务。
• 匹配 (Matching)：一个边的集合，其中任意两条边都没有公共顶点。你可以理解为给部分工人和任务的配对关系，一个工人最多只能做一个任务。
• 完美匹配 (Perfect Matching)：如果一个匹配包含了图中所有的顶点，那么它就是一个完美匹配。
• 最大匹配 (Maximum Matching)：在所有可能的匹配中，包含边数最多的那个匹配。
• 增广路径 (Augmenting Path)：从一个未匹配的顶点出发，经过一系列未匹配边、匹配边、未匹配边…最终到达另一个未匹配顶点所构成的路径。匈牙利算法的核心就是不断寻找增广路径来“腾挪”位置，从而增加匹配的边数，直到无法再找到，此时便得到了最大匹配。
• 饱和：点集均匹配

  

  https://www.bilibili.com/video/BV1jT411R7vQ/

  

  S为起点，T为终点，N(S)为邻集，N(S)-T为可选点，M为路径

算法流程与实例（这里是带权匹配的匈牙利算法）

建议看https://www.hungarianalgorithm.com/examplehungarianalgorithm.php给的例子

如何判断用最小的线覆盖所有的零

柯尼希定理

用代码实现“最少线条覆盖所有零”的过程，本质上是将这个矩阵问题转化为图论中的经典问题：二分图的最小顶点覆盖（Minimum Vertex Cover）。 在图论中有一个非常著名的柯尼希定理（König’s Theorem），它指出：在一个二分图中，最小顶点覆盖数等于最大匹配数。 假设你面对一个包含多个 0 的矩阵。 前置准备：寻找独立零，行有独立划掉列，列有独立划掉行

1. 找出行中唯一的 0，给它画上圈（表示已分配）。画圈后，将该圈所在的列中的其他 0 划掉（表示被排除）。
2. 找出列中唯一的 0，给它画上圈。画圈后，将该圈所在的行中的其他 0 划掉（表示被排除）。
3. 重复上述操作，直到不能再画圈为止。 正式开始画线（打勾法）：

• 步骤 1： 对所有没有圈的行打勾（✓）。
• 步骤 2： 观察所有刚刚打勾的行，如果这些行里面有 0（不管是被圈住的还是被划掉的），就对这些 0 所在的列打勾。
• 步骤 3： 观察所有刚刚打勾的列，如果这些列里面有被圈住的 0，就对这个 0 所在的行打勾。
• 步骤 4： 重复步骤 2 和步骤 3，直到不能再增加任何新的勾为止。
• 步骤 5：画线！ 对所有没有打勾的行画一条横线，对所有已经打勾的列画一条竖线。 如果画出的线数 等于 矩阵的阶数，则算法结束，否则 找到未被线覆盖元素中最小的，将未被线覆盖的元素都减去这个最小值，并将它加到被线覆盖了两次的元素上。

DFS+柯尼希定理

DFS 其实就是解决无权二部图的匹配问题。可以把 0 看作结点之间有边，然后先行再列的进行搜索，这样就能找到每列的 独立0。 再利用柯尼希定理进行 BFS，没有 独立 0 的行若有 0，则该列划线，若该列有 独立0，则对 独立0 所在行进行列搜索，若有 0 则该列划线，再看该列有没有 独立0，依次进行。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

import java.util.*;
public class MinimumZeroCover {
    /**
     * 计算并返回覆盖矩阵中所有0的最少线条
     * @param matrix 经过规约后的代价矩阵（关注里面的0）
     */
    public static void findMinimumLines(double[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        // 记录列匹配到的行索引
        int[] matchCol = new int[cols];
        Arrays.fill(matchCol, -1);
        // 记录行匹配到的列索引 (方便后续找未匹配的行)
        int[] matchRow = new int[rows];
        Arrays.fill(matchRow, -1);

        // ==========================================
        // 阶段 1：寻找二分图的最大匹配 (寻找相互独立的 0)
        // ==========================================
        for (int i = 0; i < rows; i++) {
            boolean[] visitedCol = new boolean[cols];
            dfsMatch(i, matrix, visitedCol, matchCol, matchRow);
        }

        // ==========================================
        // 阶段 2：利用柯尼希定理寻找最小顶点覆盖 (程序化打勾法)
        // ==========================================
        boolean[] visitedRow = new boolean[rows];
        boolean[] visitedCol = new boolean[cols];
        Queue<Integer> queue = new LinkedList<>();

        // 步骤 1: 找出所有【未匹配的行】，将它们作为交替路的起点
        for (int i = 0; i < rows; i++) {
            if (matchRow[i] == -1) {
                queue.offer(i);
                visitedRow[i] = true; // 标记为已访问 (相当于打勾)
            }
        }

        // 步骤 2 & 3: 顺藤摸瓜，遍历交替路 (BFS)
        while (!queue.isEmpty()) {
            int r = queue.poll();
            // 遍历该行所有的 0
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 0 && !visitedCol[c]) {
                    // 遇到了 0 所在的列，标记该列 (对列打勾)
                    visitedCol[c] = true;
                    // 如果这列已经分配给了某个行，就把那个行拉进来继续找 (对行打勾)
                    int matchedR = matchCol[c];
                    if (matchedR != -1 && !visitedRow[matchedR]) {
                        visitedRow[matchedR] = true;
                        queue.offer(matchedR);
                    }
                }
            }
        }

        // ==========================================
        // 阶段 3：输出结果 (划线规则)
        // ==========================================
        List<Integer> lineRows = new ArrayList<>();
        List<Integer> lineCols = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            // 规则：对【未访问】的行划线
            if (!visitedRow[i]) {
                lineRows.add(i);
            }
        }
        for (int j = 0; j < cols; j++) {
            // 规则：对【已访问】的列划线
            if (visitedCol[j]) {
                lineCols.add(j);
            }
        }

        System.out.println("最少需要 " + (lineRows.size() + lineCols.size()) + " 条线覆盖所有的 0。");
        System.out.println("划横线的行 (Row index): " + lineRows);
        System.out.println("划竖线的列 (Col index): " + lineCols);
    }

    /**
     * 基础版匈牙利算法的 DFS 寻轨
     */
    private static boolean dfsMatch(int row, double[][] matrix, boolean[] visitedCol, int[] matchCol, int[] matchRow) {
        for (int col = 0; col < matrix[0].length; col++) {
            // 寻找包含 0 且在当前寻轨中未被访问过的列
            if (matrix[row][col] == 0 && !visitedCol[col]) {
                visitedCol[col] = true;
                // 如果该列尚未匹配，或者原本匹配的行能腾出位置 (找到增广路)
                if (matchCol[col] == -1 || dfsMatch(matchCol[col], matrix, visitedCol, matchCol, matchRow)) {
                    matchCol[col] = row;
                    matchRow[row] = col;
                    return true;
                }
            }
        }
        return false;
    }

    // 测试用例
    public static void main(String[] args) {
        // 假设这是一个经过行列规约后的矩阵，里面的 0 需要被覆盖
        double[][] matrix = {
            { 0,  2,  0,  4 },
            { 1,  0,  3,  0 },
            { 0,  4,  5,  6 },
            { 7,  0,  8,  9 }
        };

        System.out.println("开始计算...");
        findMinimumLines(matrix);
    }
}

这段代码中最精妙的部分在于 阶段 2 和 阶段 3，它完全抛弃了人类视觉上的“尝试和试错”，转而利用状态机的流转来达成目的：

1. matchRow[i] == -1： 对应打勾法的“找出所有没有圈的行”。我们将这些行加入 BFS 的队列作为起点。
2. !visitedRow[i] 划横线： 为什么是对未访问的行划线？因为如果一个行被访问了，说明它是从一个未匹配点出发的交替路的一部分；如果它未被访问，说明它包含的那个独立 0 的列没有别的选择了，必须用一条横线把它封死。
3. visitedCol[j] 划竖线： 为什么是对已访问的列划线？因为在这个交替树里的列，包含了导致冲突的 0，我们无法用横线去盖住它对应的未匹配行，所以只能退而求其次，用竖线把这列的 0 全盖住。 这段代码的时间复杂度主要是求最大匹配的 $O(V \cdot E)$，在矩阵中也就是 $O(N^3)$。这是一种非常纯粹、无歧义的寻找矩阵最小覆盖的方法，在编写诸如分配优化系统、运筹学仿真器时非常实用。

最大流

待补充

KM算法

参考 [https://www.bilibili.com/video/BV1fT411977g/]

数学表示

这里 S 是 冲突的 x结点，T 是 冲突 y结点

例子

2. 我们用刚才代码里的那个 $3 \times 3$ 矩阵来做一个详细的手工推演。

假设我们有 3 个工人（$X_1, X_2, X_3$）和 3 个任务（$Y_1, Y_2, Y_3$），他们完成不同任务的产出（权重）如下表：

我们的目标是找出一个匹配方案，让总产出最大。

第一步：初始化“期望”与“要求”（顶标）

• 左侧 $X$(工人) 的初始期望 $L(x)$： 设为自己能产生的最大权重。

  • $L(X_1) = \max(3, 0, 4) = 4$
  • $L(X_2) = \max(2, 1, 3) = 3$
  • $L(X_3) = \max(0, 0, 5) = 5$

• 右侧 $Y$(任务) 的初始要求 $L(y)$： 全部设为 0。

  • $L(Y_1) = L(Y_2) = L(Y_3) = 0$

• 寻找相等边： 此时，只有满足 $L(x) + L(y) = W(x, y)$ 的边才能进入“相等子图”。

  • $X_1 - Y_3$: $4 + 0 = 4$ (进入子图)
  • $X_2 - Y_3$: $3 + 0 = 3$ (进入子图)
  • $X_3 - Y_3$: $5 + 0 = 5$ (进入子图)

• 其他边都不满足，暂时被忽略。

第二步：开始匹配（冲突与降薪）

1. 为 $X_1$ 找匹配： $X_1$ 在相等子图中只连了 $Y_3$，且 $Y_3$ 没人占，直接匹配：$X_1 \rightarrow Y_3$。

2. 为 $X_2$ 找匹配： $X_2$ 在相等子图中也只连了 $Y_3$，但 $Y_3$ 被 $X_1$ 占了。

触发“腾位置”协商：我们问 $X_1$ 能不能换个任务？$X_1$ 看了看自己所在的相等子图，发现自己除了 $Y_3$ 没别的边了，协商失败。 此时，参与协商的左侧节点是 ${X_1, X_2}$，右侧节点是 ${Y_3}$。

触发“降薪”机制 (调整顶标)： 我们需要让新的边加入进来。计算最小妥协量 $\Delta$： 看那些参与协商的工人（$X_1, X_2$）与未参与协商的任务（$Y_1, Y_2$）之间的差值 $L(x) + L(y) - W(x,y)$：

• $X_1$ 连 $Y_1: 4 + 0 - 3 = 1$
• $X_1$ 连 $Y_2: 4 + 0 - 0 = 4$
• $X_2$ 连 $Y_1: 3 + 0 - 2 = 1$
• $X_2$ 连 $Y_2: 3 + 0 - 1 = 2$
• 最小的差值 $\Delta = 1$。

更新顶标：

• 参与协商的工人降薪：$L(X_1)$ 变成 $3$，$$L(X_2)$ 变成 $2$。
• 参与协商的任务提要求：$L(Y_3)$ 变成 $1$。
• (没参与的 $X_3, Y_1, Y_2$ 顶标不变)

重新检查相等子图： 此时 $L(x) = [3, 2, 5]$，$L(y) = [0, 0, 1]$。 新加入的相等边：$X_1-Y_1$ ($3+0=3$)， $X_2 - Y_1$ ($2+0=2$)。 现在 $X_2$ 可以匹配 $Y_1$ 了。 当前匹配：$X_1 \rightarrow Y_3$, $X_2 \rightarrow Y_1$。

第三步：最后的连锁反应

1. 为 $X_3$ 找匹配：

• $X_3$ 想匹配 $Y_3$（因为 $L(X_3) + L(Y_3) = 5 + 1 = 6 \neq 5$），$X_3$ 找不到任何相等边。

• 此时 $S={x_3},,N_{G_2}(S)=T=\emptyset$，计算 $\alpha_2=\min{l(x) + l(y) -\omega(x,y)|x\in S,,y\in V_2-T}=1$

• 更新顶标：$L(X_3)$ 降为 $4$。

• 此时 $L(X_3) + L(Y_3) = 4 + 1 = 5$，$X_3-Y_3$ 重新成为相等边。 $X_3$ 尝试匹配 $Y_3$。$Y_3$ 被 $X_1$ 占了。 $X_1$ 尝试腾位置：$X_1$ 发现自己还有相等边连着 $Y_1$。但 $Y_1$ 被 $X_2$ 占了。 $X_2$ 尝试腾位置：$X_2$ 发现自己没有其他相等边了，协商再次失败！

再次大规模调整顶标： 参与协商的集合：$X = {X_1, X_2, X_3}$, $Y = {Y_1, Y_3}$。 计算出新的 $\Delta = 1$（通过 $X_2$ 连 $Y_2$ 的差值算得）。

更新顶标：

• $L(X_1)$ 降为 $2$, $L(X_2)$ 降为 $1$, $L(X_3)$ 降为 $3$。
• $L(Y_1)$ 升为 $1$, $L(Y_3)$ 升为 $2$。

奇迹时刻（重新找增广路）： 此时的相等边有：$X_1-Y_1$, $X_1-Y_3$, $X_2-Y_1$, $X_2-Y_2$ (新加入), $X_3-Y_3$。

连锁腾位置成功：

1. $X_3$ 拿走 $Y_3$。
2. 被挤掉的 $X_1$ 去拿 $Y_1$。
3. 被挤掉的 $X_2$ 去拿 $Y_2$。

最终匹配方案：

• $X_1 \rightarrow Y_1$ (权重 3)
• $X_2 \rightarrow Y_2$ (权重 1)
• $X_3 \rightarrow Y_3$ (权重 5)
• 最大总权重 = $3 + 1 + 5 = 9$。

手写过程