冒泡ioa
冒泡ioa

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

题目链接

题目大意

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

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

题解

考虑二分图匹配

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

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

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

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

代码

发表评论

textsms
account_circle
email

冒泡ioa

[CF1139E]Maximize Mex(二分图最大匹配)
题目链接 题目大意 有 $n$ 个学生 $m$ 个社团,每个学生有一个能力值 $p_i$ 属于 $c_i$ 社团,接下来的 $d$ 天里,每天由校长钦点一个学生滚蛋,然后由你从每个社团选一个人(没人就不…
扫描二维码继续阅读
2019-04-17