菜王的 blog

首先题面可以转化成：有 $a + b$ 个点，请你连接最少的边使得最大独立集大小 $< b$。

然后可以考虑手玩一下 $b = 3$ 的情况或者直接思考，发现图的形态一定是 $b - 1$ 个团，这是因为，如果不是选择了 $b - 1$ 个团，考虑对于某种最大独立集的方案，我们一定可以删除多余的边使得恰好剩下 $b - 1$ 个团且每个在最大独立集中的点都在其中一个团里。

那么使这些团的大小最为接近显然是最优的。答案可以 $O(1)$ 计算。