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)$ 。

CVBB ACM Team

用户工具

站点工具

页面工具