问题求解III-HW12 题解
Problem A: 探索遗迹 II
- 给定一棵 $n$ 个节点的带权有根树，求树上的一个最大权独立集。
- $n\leq 10^5$。
本题和 3-7 的第二题“万圣节舞会”重复。
Problem B: 探索遗迹 III
- 给定一张 $n$ 个点 $m$ 条边的有向图，求每个顶点可以支配的点的个数。这里点 $i$ 支配点 $j$ 指从图的1号点出发，任意一条到 $j$ 的路径都会经过 $i$。
- $n\leq 5000, m\leq 10000$。
本题数据范围不大，因此可以采用暴力搜索的方式通过本题——先计算从1号点出发能到达的点的数目，再计算从1号点出发不经过 $i$ 能到达的点的数目，两者的差值即为 $i$ 支配的点的数目。对每个点进行搜搜的复杂度为 $O(n+m)$，因此该做法总时间复杂度为 $O(n^2 + nm)$。
更快的做法？
如果你感兴趣，可以阅读这篇介绍支配树和使用 Lengauer-Tarjan 算法求解支配树的 文章。
支配问题在编译优化领域有着重要的应用。简单来说，在控制流图中编译器可以通过支配关系分析识别出“循环”结构，而针对循环，编译器可以采取循环不变式外提等手段进行优化。感兴趣的同学可以在编译课程中深入学习。