题目链接 题解 把人走的点当作左部节点,🐕走的当作右部 对于每个人走的节点,如果他与下一个节点的距离的两倍大于某个从当前节点走到右部节点+右部节点走到下一节点的距离,即可连边 输出方案的话,注意到如果右部节点被匹配,ma…
标签:最大匹配
[ZJOI2007]矩阵游戏(最大匹配)
题目链接 题解 两眼题 考虑每一行,如果当前列为1,则行与列连边 于是我们左部是每一行,右部是列,可以发现,如果有解,当且仅当每一列都有行与之匹配 跑匈牙利即可 代码 [crayon-6002a1de2412172204…
[CF1139E]Maximize Mex(二分图最大匹配)
题目链接 题目大意 有 n 个学生 m 个社团,每个学生有一个能力值 p_i 属于 c_i 社团,接下来的 d 天里,每天由校长钦点一个学生滚蛋,然后由你从每个社团选一个人(没人就不选),对于每天,求这些人 p_i 的 …