题解

思路

若一组软件形成依赖环，那么安装其中任意一个能够正常工作的软件都必须同时安装环内全部软件。可以先把每个依赖环合并成一个整体，再处理整体之间的依赖关系。

每个软件至多依赖一个软件。缩点之后，每个合并点也至多依赖一个合并点，因此把依赖方向反过来后会得到一片森林：父结点是必须先安装的依赖，子结点是依赖它的软件。增加一个重量和价值均为零的虚拟根并连接所有无依赖的合并点，就得到一棵树。

做法

先在依赖图上求强连通分量。对每个分量累加其中软件的磁盘占用和价值。若某个分量依赖另一个分量，就从被依赖分量向它连边；没有依赖的分量连接到虚拟根。

在缩点树上进行树形背包。对于真实结点，初始状态只允许选择整个分量，其初始容量为分量总占用、价值为分量总价值；虚拟根的初始状态为容量零、价值零。依次合并每棵子树：可以完全不选该子树，也可以选择该子树中某个合法状态。由于子树状态只能从已经选择父结点的状态转移，依赖条件自动得到满足。

最终取虚拟根在容量不超过 $M$ 的所有状态中的最大值。

正确性证明

同一强连通分量内的软件沿依赖关系互相可达。若其中一个软件正常工作，则其全部直接和间接依赖都必须安装，所以整个分量必须同时安装；反之，同时安装分量内全部软件即可满足分量内部依赖。因此把每个分量合并为一个整体不改变最优答案。

缩点后不存在依赖环，且每个结点至多有一个依赖父结点。树形背包中，任何被选择的非根结点都通过与父结点已有状态的合并进入答案，所以其父结点以及递归向上的全部依赖一定已被选择。反过来，任意满足依赖条件的安装方案在每棵子树中都对应一个合法状态，并会在合并过程中被枚举。因此动态规划恰好覆盖全部合法方案，得到最大价值。

复杂度

• 时间复杂度：$O(N+M N+N M^2)$，通常记为 $O(NM^2)$。
• 空间复杂度：$O(NM+N)$。