我有一个分配问题的变体，通常的Munkres/匈牙利算法似乎无法解决。
在传统的分配问题中，有n个工人需要被分配到n个工作，并且矩阵包含将每个工人分配到每个工作的成本。
在这个变体中，我们只有m（m<n）个工人。由于Munkres算法需要相等数量的工人和工作岗位，我们创建了（n-m）个可以分配到空闲工作岗位的"虚拟"工人。此外，工作本身被组织成大量离散的类别。
我们希望强加一个约束，即每个类别中至少有一个工作分配给一个真实（非虚拟）工人。这很难做到：例如，你可以从每个类别中随机挑选一份工作，人为地降低每个真正的工人的相关成本，但这是一个非常粗糙的解决方案，严重损害了最终任务的完整性。
我们目前所做的是多次运行该算法，每次都评估输出分配，然后修改成本矩阵，以便任何类别中仅分配虚拟工人的所有作业的成本都会略有降低。这是有效的，但对于中等规模的数据集（n~=500），这个过程可能需要一段时间（每个Munkres赋值可能需要10秒的计算时间，如果有足够的类别，可能会有不平凡的迭代次数）。
有没有一种改进的Munkres算法，或者完全不同的算法，可以更有效地解决这个问题？
类别是否不相交？每个工作都有一个类别？那么，最低成本流如何？
节点类型：
SRC - source
SNK - sink
C - a node or each category
J - a node for each job
W - a node for each worker
连接：
1) from SRC to C, capacity 1, cost 0
2) from SRC to C, capacity infinite, cost a high number
3) from C to J, capacity 1, cost 0
4) from J to W, capcity 1, the cost of job J done by worker W
5) from W to SNK, cost 0, capacity 1
然后，算法将首先填充类型为1的链接，这意味着每个类别将至少有一个工作者（如果可能的话）。