‹ 上一题 下一题 ›

g6-07572. 叶子贪心·什么时候够、什么时候不够 未做

1000 ms 256 MB 测试点 ? 自拟题知识点题GESP-66级·树形 DP 入门客观题单选

最大匹配(选尽量多的边、任意两条无公共端点)。有人说:「从叶子往上贪心,每个没配对的叶子尽量和它的父亲配对,就能得到最大匹配。」这个说法( )。

  • A. 对树来说这个贪心确实能得到最大匹配(叶子只有父亲一个可选,配给父亲不亏);但它只是树的特例,换成「带权匹配 / 独立集」等约束贪心就失效,所以要学通用的 DP 骨架
  • B. 贪心对任意图都成立
  • C. 贪心一定错,只能 DP
  • D. 贪心与 DP 结果不同,只能相信 DP
未选择
输入
输出

            
答案