具有更新的节点加权DAG和最长路径

Question

假设您有一组可以并行完成的作业。每个工作都有时间要求（第i个工作的时间要求是t_i）。还有一些依赖关系，他们中的第一个说你必须在工作v_i之前做u_i工作。你必须最小化所需的总时间。

这很容易通过将这些关系转换为有向无环图，然后使用它来确定哪些要并行执行。

如果我不清楚，这里是一个例子。假设你有5个工作时间要求为2,9,3,12,5，你必须在5之前4，5之前3，之前1和之前1之前做3。然后你能做的最好的是17。您的DAG：

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

您可以同时做3和4，让你花MAX（3,12）= 12个单位的时间做5，这需要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 maxima，这是一个计算几何学研究得很好的问题，对于预分类输入（至少在二维中），已知的最快的n个算法是O（n log log n），通过van Emde Boas树，在一些情况下，存在输出敏感时间范围比最坏情况范围更好的算法。）