洛谷4258 [WC2016]挑战NPC
Luogu UOJ 分析 考虑把每个筐子拆成三个点，三个点间互相连边，然后每个球向能放的筐子拆成的三个点连边。 考虑这张图的一个最大匹配：如果某个筐子匹配了 $0$ 个球，那么会贡献 $1$ 个匹配；如果匹配了 $1$ 个球，那么会贡献 $2$ 个匹配；如果匹配了 $2$ 或 $3$ 个球，那么会贡献 $2$ 或 $3$ 个匹配。 也就是说，半空的筐子贡献的匹配数恰为匹配的球数加 $1$。 ...
Luogu UOJ 分析 考虑把每个筐子拆成三个点，三个点间互相连边，然后每个球向能放的筐子拆成的三个点连边。 考虑这张图的一个最大匹配：如果某个筐子匹配了 $0$ 个球，那么会贡献 $1$ 个匹配；如果匹配了 $1$ 个球，那么会贡献 $2$ 个匹配；如果匹配了 $2$ 或 $3$ 个球，那么会贡献 $2$ 或 $3$ 个匹配。 也就是说，半空的筐子贡献的匹配数恰为匹配的球数加 $1$。 ...