本文主要是介绍uva 10859 - Placing Lampposts(树形dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:uva 10859 - Placing Lampposts
题目大意:给定一个无向无环图,要求在点上放灯,如果某一点上放了等,则可以照亮与它相通的边,现在要求放尽量少得等,使得所有边都被照亮,并且输出灯数,被照亮两次的边数(即边的两个端点均放置灯),被照亮一次的边。 如果等数一样的话,按照被照亮一次边越大的方案。
解题思路:树形dp,每次枚举某个顶点作为根,对于每个点有放与不放两种可能,均进行考虑;然后每放一盏灯+2000(因为边的最大数量为1000),每增加1条照亮一次的边+1.
这篇关于uva 10859 - Placing Lampposts(树形dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!