CVBB ACM Team

有 $n$ 个员工和 $n$ 个机器，每个机器至多被一个工人使用，每个工人也至多使用一个机器，第 $i$ 个工人使用第 $j$ 个机器的贡献是 $a_i+b_j$ 。且有 $m$ 对关系，表示员工 $i$ 不能使用机器 $j$ 。现在要对于每个 $k=1,……,n$ ，求出恰有 $k$ 对使用的情况下的最大贡献。

$n\le 4000,\ m\le 10000$

考虑一个显然的费用流模型，源点连向员工，员工连向可使用的机器，机器连向汇点。然后每次更新1流量，之后输出结果。

但是这个简单的过程复杂度不太够，考虑优化每次增广的过程：我们注意到每次本质上是会多出来一对员工和机器，那么我们考虑去BFS找到每个机器能被最大多少权值的员工到达。这个过程就是按权值从大到小枚举员工，对于没有配对的员工开始在补图上遍历，如果遍历到的机器没有配队，那么就更新其匹配到的员工，否则就将其配对的员工加入队列继续BFS，相当于在走增广路。这样就是一个遍历补图的复杂度就可以更新一次流量，单次复杂度就是 $O(n+m)$ 。