金融信创如何推动金融服务效率与安全的全面提升
598
2022-10-20
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小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~