将分配问题转换为最大流问题
convert assignment problem to The Maximum Flow Problem
根据我在这篇link中读到的article，赋值问题在一定条件下可以转化为最大流问题。
我知道最小成本流问题的转换，但我想知道从这个方法，在什么条件下这个问题变成最大流问题？
当所有允许的分配具有完全相同的权重时，分配问题可以转换为单个最大流问题。这个想法是制作一个二分图（加上全局源节点和汇节点），每个人和该人的每个允许任务之间的边缘容量为 1，然后看看是否可以找到一个值等于可用人数的流。如果可以，那么流量代表的是人到任务的分配。
这篇文章解释了如何将更一般的分配问题转换为解决一系列最大流问题。 （分配问题可以转化为最小成本流问题。解决最小成本流问题的一种方法是 Kuhn-Munkres 算法。Kuhn-Munkres 算法通过解决许多最大匹配问题来工作。每个最大匹配问题可以转化为最大流问题。）
根据我在这篇link中读到的article，赋值问题在一定条件下可以转化为最大流问题。 我知道最小成本流问题的转换，但我想知道从这个方法，在什么条件下这个问题变成最大流问题？
当所有允许的分配具有完全相同的权重时，分配问题可以转换为单个最大流问题。这个想法是制作一个二分图（加上全局源节点和汇节点），每个人和该人的每个允许任务之间的边缘容量为 1，然后看看是否可以找到一个值等于可用人数的流。如果可以，那么流量代表的是人到任务的分配。
这篇文章解释了如何将更一般的分配问题转换为解决一系列最大流问题。 （分配问题可以转化为最小成本流问题。解决最小成本流问题的一种方法是 Kuhn-Munkres 算法。Kuhn-Munkres 算法通过解决许多最大匹配问题来工作。每个最大匹配问题可以转化为最大流问题。）