指派问题

指派问题是一类常见的优化问题，大概意思是合理分配资源，让总体代价最小。

分配问题一般可以用二分图来表示，所谓的二分图，就是指所有顶点能够排成两列，列内部没有连线，连线只存在两列之间，如下图所示。

为什么要求必须是二分图呢？因为这样就能够把左侧那一列当做资源，右侧那一列当做任务，中间的连线可以当做资源分配给这个任务所需要的代价。

如果像上图那样，边并不带权值，说明这里的代价是0-1布尔型，这时候能够用到max flow算法，例如 Hopcroft-karp算法，通过反转增广路径找到最大匹配来实现指派问题求解, 复杂度O(|E| * sqrt(|V|)) .

如果是带有权值的边，那么问题就会相对复杂，这时候可以使用匈牙利算法或者Min cost max flow 法求解，复杂度能够优化到O(n^3) .