csu1580 树形依赖背包模板题

题意

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

思路

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

题解链接

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!