某工厂分配四个工人甲、乙、丙、丁同时去操作四台机床A、B、C、D，每人分配其中的一台。已知每个工人操作每台机床每小时的效益值如下表所示，则总效益最高的最优分配方案共有（__）个。
指派问题是运筹学中经典的一对一匹配优化问题，适用于n个任务与n个执行者的精准分配场景，目标通常为实现总成本最小或总效益最大。针对总效益最大化的场景，需先将效益矩阵转换为等价的成本矩阵，转换规则为取矩阵中的最大值，用该值减去矩阵内每个元素，将问题转化为成本最小化问题后，可通过匈牙利算法求解。匈牙利算法的关键流程为：首先对矩阵执行行规约，即每行所有元素减去该行的最小值；接着执行列规约，即每列所有元素减去该列的最小值；随后用最少的直线覆盖矩阵中所有0元素，若覆盖直线的数量等于矩阵的阶数n，即可从0元素中选取每行、每列各一个的独立0元素组合，每个合法组合对应一个最优分配方案；若覆盖直线数量小于n，则对未被覆盖的元素减去未覆盖区域的最小值，直线交叉点的元素加上该最小值，重复操作直至覆盖直线数等于n。最优方案的数量由独立0元素的不同有效组合数决定，需逐一梳理所有符合行、列唯一匹配要求的组合。这类问题可拓展应用于人员任务调度、设备资源分配、项目角色指派等诸多场景，在中小规模的匹配需求中，匈牙利算法是高效且精准的求解方法。
本题考察的是指派问题中最优方案数量的计算，用匈牙利算法。此题属于进阶难度。需要掌握补 0 还有成本矩阵转化的技巧。
我们现在要解决的题目是：工人 × 机床的“指派问题”，每个工人对不同岗位有一个“效益值”，我们要让总效益最大。
而匈牙利算法原始设计时，是用来解决：每个人干一件事，总成本最小的问题。
两者在数学模型上是对偶关系（结构一样，但目标方向相反）：我们不能直接把最大效益套进匈牙利算法。但有一个方法可以“变形”它，让它变成可以处理的“最小化问题”。这个方法叫：效益矩阵转为成本矩阵：每个值 = 当前最大值 − 原值，这个矩阵最大值是 6，各个元素用 6 去减得到下面的矩阵，
对于这个矩阵首先还是对矩阵进行行规约（每行元素减掉这行的最小值），得到下面的矩阵。
再进行列规约得到下面矩阵（每列元素减掉这行的最小值）
此时发现只要三条线就可以覆盖所有的 0 元素，小于矩阵的阶数 4，需要通过变换补全。
根据匈牙利算法：
未覆盖元素减去最小值 1。 交叉点元素加上最小值 1。覆盖线下元素保持不变。调整后矩阵：
根据这里的零元素进行指派：
方案 S1： 甲工人分配到机床 A，乙工人分配到机床 C，丙工人分配到机床 B，丁工人分配到机床 D，总效益为 5 + 5 + 3 + 5 = 18。
方案 S2： 甲工人分配到机床 C，乙工人分配到机床 B，丙工人分配到机床 A，丁工人分配到机床 D，总效益同样达到 5 + 4 + 4 + 5 = 18。
方案 S3： 甲工人分配到机床 C，乙工人分配到机床 D，丙工人分配到机床 B，丁工人分配到机床 A，计算得到的效益也是 5 + 6 + 3 + 4 = 18。