

$18.$分配问题

题目

有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案，使产生的总效益最大。 一个人只能修一个工件。 两行分别输出最小总效益和最大总效益。

题解

最小费用最大流，人放左边，商品放右边，$S$ 向人连 $(1, 0)$的边，商品向 $T$ 连 $(1, 0)$ 的边，人向商品连 $(1,c[i][j])$ 的边，因为每个人只能修一个工件，所以流量最大为 $1$。 然后跑费用流。 好像可以用二分图最佳完美匹配的 $KM$ 算法做，到时候学一下去。