题意
有一辆能载客m的车,有n个人,然后第i个人上车的条件是第a[i]个人要上车,问最多能上几个。
(题意很简单吧。)。
思路
首先要明确一点,这些人的依赖可能会成环,也就是说一群人要一起上才行,不存在你上我不上的
情况,面对这个我们就要用有向图的强联通分量进行缩点了,缩完点之后就得到了森林(很多根节点)。
子树是依赖于根节点的,这就变成了典型的树形依赖背包了,另外想着加一个超级根节点将森林搞成树
就好了。
原文链接:/javaschema/284409.html
有一辆能载客m的车,有n个人,然后第i个人上车的条件是第a[i]个人要上车,问最多能上几个。
(题意很简单吧。)。
首先要明确一点,这些人的依赖可能会成环,也就是说一群人要一起上才行,不存在你上我不上的
情况,面对这个我们就要用有向图的强联通分量进行缩点了,缩完点之后就得到了森林(很多根节点)。
子树是依赖于根节点的,这就变成了典型的树形依赖背包了,另外想着加一个超级根节点将森林搞成树
就好了。