HAOI2010

题意:给定一些软件,每个软件占Wi空间,价值Vi,依赖第Di个软件。求在M空间的电脑最多可以装多少价值的软件。软件i可以安装当且仅当软件Di已安装,默认Di=0意思是没有依赖,可以随意安装。

思路,由于图中相当于有n个节点,n条边,所以必定有自环。我们可以用Tarjan判环缩点(当然我用的不是,我不会打),再进行树上背包。

问题一:缩点。%%%HZWER%%%用的是Tarjan(行数稍稍多了点),貌似很高级,但是我不会打Tarjan,于是我经过思考,想到了一个根据这幅图特性得出的专用判环函数(貌似思想和Tarjan一样,只是行数少)

判环缩点函数:

再main函数中:

十二行搞定判环缩点。此时就可以把每一种颜色(color数组)当成一个点,建树,建树的同时弄树上背包。对于每个子节点当成一个分组,进行分组背包问题,物品的大小就是分配的空间。由于子节点可以选的前提是父节点已选,所以有这么一句:

这个代码差不多可以称全网较短了。