题意： 已知一棵树...求用最小的点覆盖所有的边 .匈牙利算法的时间复杂度是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,,,纪念....