[CF1139E]Maximize Mex(二分图最大匹配)

发布于 2019-04-17  53 次阅读


题目链接

题目大意

有 $n$ 个学生 $m$ 个社团,每个学生有一个能力值 $p_i$ 属于 $c_i$ 社团,接下来的 $d$ 天里,每天由校长钦点一个学生滚蛋,然后由你从每个社团选一个人(没人就不选),对于每天,求这些人 $p_i$ 的 $mex$ 的最大值

$mex$ 即为序列中最小的非负整数

题解

考虑二分图匹配

左部为学生的能力值,右部为社团。

将学生的能力值与其社团连边。

从最后一天开始匹配,往前的话,由于人只多不少, $mex$ 不会减少(最坏的情况你都可以选择上一次的人员构成)

代码里都加了一,最后答案减了一,这是因为我写的链式前向星和匈牙利不能有0元素(其实稍微改改也行)

代码


哇,你居然发现了这里!