UVA 10461差异问题的解决方法

问题描述 投票:-1回答:1

我不明白如何解决此问题-UVA 10461

我可以看到人们两次做bfs,但是我看不到它是如何解决问题的。我只是一无所知,如果有人可以用简单的方式解释它,那将真的很有帮助。

谢谢!

algorithm data-structures
1个回答
0
投票

T最早可以执行的任务是什么?必须先执行从依赖关系箭头到T的所有任务。您可以通过从T中搜索以得出可到达节点的权重之和来找到它们。

您可以执行的最新任务是什么?从U通过依赖箭头上的向后可完成的所有任务都必须稍后执行。同样,您可以通过从U进行搜索来找到可到达节点的权重之和。

图形是DAG,不一定要连接。周期没有意义。简单的DFS就可以满足搜索要求。

还有两个子问题。首先,您要避免对N个节点的图进行2N次搜索。这不难。无论从何处开始搜索,节点子级的权重总和都是相同的,因此在边缘上向前进行一次搜索就可以找到所有最早的时间,而在边缘后边进行一次搜索就可以找到最新的时间。

第二个子问题是如何表示图形。我们最多可以有500个顶点,但最多不能有500个边。因此,该图可能是稀疏的。对于DAG SEACH最有效的是邻接表。您将需要其中两个:一个用于前边缘,另一个用于后边缘。

假设您已经建立了一个邻接表表示,其中a[i].adj是与节点i相邻(向前)的节点的列表,任务持续时间在数组d[]中。还要假设在建立邻接矩阵时,您要跟踪数组ni[]中每个顶点的边缘数。我们想将最早的时间存储在数组e[]中。

记住要搜索DAG,需要遍历所有节点以找到起点:对于前向搜索,没有边缘的节点(称为源),对于后边缘搜索没有边缘的节点(称为汇)。

然后用于正向搜索的伪代码将如下所示

def find_all_earliest()
  for i = 1 to v
    e[i] = UNASSIGNED
  for i = 1 to v
    if ni[i] = 0 // found a source
      find_earliest(i)

// Return the sum of node weights of subtree rooted at `i`.
def find_earliest(i)
  if e[i] != UNASSIGNED // Use already-computed value if there is one.
    return e[i]
  decendant_sum = 0
  for a in a[i].adj
    decendant_sum += find_earliest(a)
  e[i] = decendant_sum
  return decendant_sum + d[i]

完成后,e[i]包含任务i的最早开始时间。最新搜索将是对称的。答案是相应的最早时间和最新时间​​之间的差异。

此后,e[i]包含任务i的最早开始时间。

© www.soinside.com 2019 - 2024. All rights reserved.