algorithm - 节点加权 DAG 和带更新的最长路径

Question

假设您有一组可以并行完成的作业。每个工作都有一个时间要求(第 i 个工作的时间要求是 t_i )。还有一些依赖关系，其中第 i 个表示你必须在作业 v_i 之前完成作业 u_i。您必须尽量减少所需的总时间。

通过将这些关系转换为有向无环图，然后使用它来确定要并行处理哪些关系，可以很容易地做到这一点。

如果我不清楚，这里有一个例子。假设你有 5 个工作，时间要求为 2、9、3、12、5，你必须在 5 之前做 3，在 5 之前做 4，在 1 之前做 3，在 2 之前做 1。那么你能做的最好是 17。这是你的爸爸:

+---> 1 (2) ---> 2(9)
|
3 (3)
|
+----> 5 (5)
       ^
       |
4 (12)-+

你可以并行做3和4，这样你在做5之前花费了MAX(3,12)=12个单位的时间，这需要5个单位的时间。所以 5 在 17 个单位时间后完成。另一方面，2 在 14 个单元后完成。所以答案是 17。

问题是，如果在每个查询中只更新一个时间要求(每次您从原始图开始，而不是之前修改后产生的图)您如何有效地找到新的最短时间要求？

对于那些想要限制的人，工作数量 <= 10^5。依赖项数 <= 10^6，查询数 <= 10^6。

Answer 1

时间要求是无环有向图中一条路径的最大权值。对于每个节点，两次线性时间遍历产生以该节点结束的路径的最大权重和以该节点开始的路径的最大权重。现在我们可以找到包含指定节点的路径的最大长度。如果一个节点的权重增加，那么我们取前一个最大值的最大值和涉及该节点的新最大值，我们可以在恒定时间内计算。

减少比较棘手，因为对于最大权重路径中的每个节点，我们需要不包括该节点的路径的最大权重。我能想到的第一种方法(也许不是最好的)如下。向非循环有向图中添加一个源和一个汇，它们的权重都为零，并且连接到(源)或来自(汇)每个其他节点。按拓扑顺序对节点进行编号，其中源为0，汇为n + 1，并初始化线段树将节点映射到路径权重，其中初始值为-infinity。此线段树具有以下对数时间操作。

Weight(i) - returns the value for node i
Update(i, j, w) - updates the value for nodes i..j to
                  the maximum of the current value and w

对于从i到j的每条弧，调用Update(i + 1, j - 1, w)，其中 w 是包含从i 到j 的弧的路径的最大权重。最后，线段树中的每个权值是除去对应节点的路径的最大权值。

(关于运行时间的注意事项:通过单独处理没有依赖关系的节点，可以使该方法的运行时间为 O(m log n + n + q)，其中 n 是节点数，m 是依赖项的数量，q 是查询的数量。我的线段树排序是计算 3D 最大值，这是计算几何学家研究得很好的一个问题。对于预排序的输入(至少在二维上)，已知最快的 n 点算法是 O (n log log n)，通过 van Emde Boas 树。在某些情况下，还存在输出敏感时间界限比最坏情况界限更好的算法。)