最大匹配(选尽量多的边、任意两条无公共端点)。有人说:「从叶子往上贪心,每个没配对的叶子尽量和它的父亲配对,就能得到最大匹配。」这个说法( )。
- A. 对树来说这个贪心确实能得到最大匹配(叶子只有父亲一个可选,配给父亲不亏);但它只是树的特例,换成「带权匹配 / 独立集」等约束贪心就失效,所以要学通用的 DP 骨架
- B. 贪心对任意图都成立
- C. 贪心一定错,只能 DP
- D. 贪心与 DP 结果不同,只能相信 DP
g6-07572.in输出g6-07572.out最大匹配(选尽量多的边、任意两条无公共端点)。有人说:「从叶子往上贪心,每个没配对的叶子尽量和它的父亲配对,就能得到最大匹配。」这个说法( )。