UVa 1292 - Strategic game (树形dp)

本文出自   http://blog.csdn.net/shuangde800


题目链接: 点击打开链接

题目大意

给定一棵树,选择尽量少的节点,使得每个没有选中的结点至少和一个已选结点相邻。

思路

经典的树形dp题,据说是最小顶点覆盖。

f[u][0]: 表示不选i点,覆盖这个子树的最少点
f[u][1]:选i点,覆盖这个子树的最少点

对于u点,如果选择这个点,那么他的字节点可选也可不选
如果不选u点的话,那么它的子结点就必须要选!开始时我以为字节点只要至少选一个就可以了,但是这样是错的!

因为会出现下面这种情况:

UVa 1292 - Strategic game (树形dp)

顶点1不选,子节点中2有选了,但是3却没有相邻结点有选。

所以可以得到状态转移方程:

f[u][1] = sum{ min{f[v][0], f[v][1]}, v是u的子结点 }
f[u][0] = sum{ f[v][1], v是u的子结点 }

代码

 
上一篇:SGU 149. Computer Network( 树形dp )


下一篇:143. Long Live the Queen 树形dp 难度:0