首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
zonk专题
UVa12093 Protecting Zonk
题意:给定一个有n个节点的无根树,有两种装置A和B,每种都有无限多个。在某个节点X使用A装置需要C1的花费,并且此时与节点X相连的边都被覆盖。在某个节点X使用B装置需要C2的花费,并且此时与节点X相连的边以及与X相连的点相连的边都被覆盖。求覆盖所有边的最小花费。 思路:树型dp。随便拿一个点当作树根,dp(i,j,k),i代表节点号,j代表选择装置的类型,k代表覆
阅读更多...