根据我在此链接中阅读的文章，在某些条件下，分配问题可以变成最大流问题。我知道最小成本流问题的转换，但是我想知道从这个方法中，这个问题在什么条件下变成最大流问题？
问问题
305 次
1 回答
3
当所有允许的分配具有完全相同的权重时，分配问题可以转换为单个最大流问题。这个想法是制作一个二分图（加上全局源和汇节点），每个人和每个允许的任务之间的容量为 1 边，看看你是否能找到一个价值等于可用人数的流。如果可以，那么流程代表了人员对任务的分配。
本文解释了如何将更一般的分配问题也转化为解决一系列最大流问题。（分配问题可以转换为最小成本流问题。解决最小成本流问题的一种方法是 Kuhn-Munkres 算法。Kuhn-Munkres 算法通过解决许多最大匹配问题来工作。这些最大值中的每一个匹配问题可以转化为最大流量问题。）
于 2021-06-05T09:03:42.267 回答