最小点覆盖,求最少的点集,使得每一条边至少都有端点再这个点集中
二分图上的最小点覆盖问题定理 : 最小点覆盖 = 最大匹配 最大独立点集(在二分图中,选最多的点,使得任意两个点之间没有直接边链接
最大独立点集 = 总点数 - 最大匹配 (条件 : 在二分图中
树上的最小点覆盖问题对树进行红黑染色,相邻两个点不能是黑色的,求最小的红色点数
看上去是一个贪心,其实是一个 d p dp dp
我们记当前点 c u r cur cur为红色,其子树上红色点数为 r e d [ c u r ] red[cur] red[cur] 记当前点 c u r cur cur为黑色,其子树上红色点数为 b l a c k [ c u r ] black[cur] black[cur]
状态转移方程 : r e d [ c u r ] = 1 + ∑ m i n ( b l a c k [ n x t ] , r e d [ n x t ] ) , n x t 是 c u r 的 儿 子 red[cur] = 1 + \sum min(black[nxt],red[nxt]) , nxt是cur的儿子 red[cur]=1+∑min(black[nxt],red[nxt]),nxt是cur的儿子 b l a c k [ c u r ] = ∑ r e d [ n x t ] , n x t 是 c u r 的 儿 子 black[cur] = \sum red[nxt] ,nxt是cur的儿子 black[cur]=∑red[nxt],nxt是cur的儿子
