POJ1463 - 树型DP

网友投稿 598 2022-10-20

POJ1463 - 树型DP

POJ1463 - 树型DP

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

.匈牙利算法的时间复杂度是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,,,纪念....

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:小程序多端引流(小程序多端引流怎么做)
下一篇:企业APP开发(企业app开发制作公司)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~