匈牙利算法指派流程图

匈牙利算法的指派流程图如下所示：

1. 初始化：给定一个n x n的二维矩阵，表示任务的支付矩阵。
2. 行归约：对每一行进行归约，即找出每一行的最小值，并将该最小值从该行的每个元素中减去。
3. 列归约：对每一列进行归约，即找出每一列的最小值，并将该最小值从该列的每个元素中减去。
4. 标记零元素：在矩阵中找到所有的零元素，并进行标记。
5. 尝试匹配：从第一行开始，找到一个未被匹配的零元素，并将其标记为已匹配。如果该行中的其他零元素已经被匹配，则继续尝试下一行。
6. 增广路径：如果存在未被匹配的零元素，通过增广路径的方式将其匹配。增广路径是指从一个未匹配的零元素出发，依次经过已匹配的零元素，再到下一个未匹配的零元素，直到无法继续增广为止。
7. 修改匹配：根据增广路径，修改当前的匹配情况。对于增广路径上的已匹配零元素，将其变为未匹配；对于增广路径上的未匹配零元素，将其变为已匹配。
8. 清除标记：清除所有的标记。
9. 重复步骤5-8，直到无法找到增广路径为止。10. 最终匹配：根据最终的匹配情况，得到任务的最优分配方案。

相关问题

匈牙利算法 指派问题

匈牙利算法是一种解决指派问题（Assignment Problem）的经典算法。指派问题是一类优化问题，其目标是在给定的n个任务和n个执行者之间建立最佳的一对一的任务分配方案，使得总的分配成本最小化。

匈牙利算法的基本思想是通过构建增广路径来逐步改善当前的分配方案，直到找到最优解。它的核心步骤包括：

1. 初始化：为每个任务和执行者找到一个初始的分配方案。
2. 寻找增广路径：在当前分配方案下，通过搜索增广路径来找到未分配任务的最佳分配执行者。
3. 改善分配：根据找到的增广路径，改善当前分配方案，使得已分配任务得到更优的执行者。
4. 终止条件：当无法找到增广路径时，当前分配方案即为最优解。

匈牙利算法的时间复杂度为O(n^3)，其中n为任务或执行者的数量。它在实际应用中被广泛用于解决各种任务调度、资源分配等问题。

匈牙利算法指派问题出现负数

匈牙利算法是解决二分图最大匹配的经典算法之一，它的核心思想是不断寻找增广路，直到找不到为止。在实际问题中，指派问题中出现负数是比较常见的情况。一般来说，如果出现负数，我们需要将所有的边权值都加上一个正数，使得所有边权值变为正数，这样就可以继续使用匈牙利算法求解了。

举个例子，假设我们有一个二分图，左侧顶点集合为{A,B,C}，右侧顶点集合为{X,Y,Z}，其中边权如下：

A->X: 2
A->Y: -1
B->X: 4
B->Y: 3
C->X: -5
C->Y: 2

可以看到，边权中出现了负数。我们可以将所有的边权值都加上一个正数，比如6，使得所有边权值变为正数：

A->X: 8
A->Y: 5
B->X: 10
B->Y: 9
C->X: 1
C->Y: 8

然后再使用匈牙利算法求解即可。