题解：P10935 银河

D_chzhh_L · 2024-08-26 09:08:01 · 题解

前置知识：差分约束 + 强连通 Tarjan + 拓扑 DP。

差分约束：

注意到，题目中所给出不等关系的约束都可以用 x \ge y 以及 x > y 来表示，同时 x \ge y 和 x > y 又可以用 x \ge y + z 来表示，也就是：

• x \ge y$ 转化为 $x \ge y + 0
• x > y$ 转化为 $x \ge y + 1

所以都可以用这一关系来建图，x \ge y + z 就是 y 向 x 连一条边，而边权就是 z。

强连通 Tarjan：

我们可以发现，当两个点在一个强连通图当中必然有这两个点的亮度相同，因为根据上述所说的建图方法能够得出来这个不小于是有传递性的，所以一条路的终点一定大于等于这一条路的起点，则成立。

因此就可以用 Tarjan 将所有的强连通预处理出来，这样子就可以把这个图变成了 DAG。

同时也可以发现，如果是这样的话，单个强连通里面的每一条边的边全都应该是 0。所以 -1 的情况，就是如果发现在单个强连通里面有出现过一条边的边权是 1 的情况。

在强连通的时候，预处理下每个强连通里面的节点数量，以后要用。

拓扑 DP：

题目中的亮度现在可以转化成从这个 DAG 的任意一点出发，所得到的最长路径的权值和是多少，发现可以用拓扑 DP 求解。

设 dp_{i} 表示，从点 i 的前驱转移到点 i 的最长路径是多少，则动态转移方程就是：dp_{i}= \max (dp_{j}+dis) 其中 j 是 i 的前驱，dis 是从 j 走到 i 的权值是多少。

初始化是假如点 i 的入度为零，则 dp_{i} = 1。

计算答案：