POJ1463如何运用树型动态规划解决？

本文共计381个文字，预计阅读时间需要2分钟。

题意：已知一棵树，要求使用最小的点覆盖所有边。牙龈算法的时间复杂度为O(n^2)。果断是要TL的...最后用到的方法就是树形DP...经过详细思考后发现也是很简单...+a[k][0] 表示不需要覆盖K个结点。

题意： 已知一棵树...求用最小的点覆盖所有的边

.匈牙利算法的时间复杂度是O(n^2)...果断是要TL的..

最后用的方法就是树型DP..仔细思考后发现也是很简单的...

a[k][0] ]表示不需要第K个结点..a[k][1]表示需要第K个结点

a[k][0]=其所有孩子的 a [ ] [ 1 ] 的和 ... 因为如果当前点不保留...而当前点到其每个孩子的边又必须要被覆盖..所以其所有孩子都需要被保留...

a[k][1]=其所有孩子的 min ( a [ ] [ 1] , a[ ] [ 0 ] ) 之和 + 1 ...应为当前点我选择了保留...则孩子的情况是有还是没有都无所谓...找到每个孩子的最小值相加再加上1就可以了..

所需要的答案则是根的 a[ roo t ] [ 0 ] 与 a [ roo t ] [ 1 ] 中较大的那个...

第一次submit的时候爆空间了....原因是我存这课树用的是邻接矩阵..改了后就Accepted了....

这道题通过率也不低..但A这道题经过不少次周折...第一道树型DP,,,纪念....