csu1580 树形依赖背包模板题

前端之家收集整理的这篇文章主要介绍了csu1580 树形依赖背包模板题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题意

有一辆能载客m的车,有n个人,然后第i个人上车的条件是第a[i]个人要上车,问最多能上几个。
(题意很简单吧。)。

思路

首先要明确一点,这些人的依赖可能会成环,也就是说一群人要一起上才行,不存在你上我不上的
情况,面对这个我们就要用有向图的强联通分量进行缩点了,缩完点之后就得到了森林(很多根节点)。
子树是依赖于根节点的,这就变成了典型的树形依赖背包了,另外想着加一个超级根节点将森林搞成树
就好了。


题解链接

猜你在找的设计模式相关文章