洛谷：P1113：杂务


洛谷：P1113：杂务

Table of Contents

题目

P1113：杂务

分析

节点的数据结构

我们看一个简单的例子：

flowchart LR A[任务1\n耗时:2]-->B[任务2\n耗时:3] A-->C[任务3\n耗时:4] B-->D[任务4\n耗时:1]

本题首先要确定如何表示这里提到的节点。对于一个特定的节点来说，它有两个核心成员：

  1. 自身需要的时间duration。
  2. 它所有的“前置”任务（或者说“依赖”任务）。“依赖”关系用邻接表是最自然的：vector<int> pre_tasks[MAXN];——用这个整数列表数组即可。

因此，节点的定义如下：

struct Task
{
    int duration;
    vector<int> pre_tasks;
};

动态规划

对于某个特定任务来说，它的结束时间是它自己需要耗费的时间加上所有“前置”任务中最后完成（max）的那个任务的时间。

for (int pre : tasks[i].pre_tasks)
{
    max_pre_time = max(max_pre_time, dp[pre]);
}
dp[i] = max_pre_time + tasks[i].duration;

完整代码如下。

答案

Solution

思考

本题引入了一个DAG的新概念。

如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（Directed Acyclic Graph，缩写：DAG）。

本题中，虽然用了DP，但其实是多余的。由于保证每个任务的前置任务的编号都比自己小，所以实际上已经有了拓扑排序。对于每个任务，我们只要从小到大遍历，并对每个任务遍历其“前置”任务并找到最大的完成时间，然后更新本任务的完成时间即可。代码可以精简为：

    for (int i = 1; i <= n; ++i) 
    {
        int current_max = 0;
        for (int pre : tasks[i].pre_tasks) 
        {
            current_max = max(current_max, tasks[pre].duration);
        }
        tasks[i].duration += current_max;
        max_time = max(max_time, tasks[i].duration);
    }

无论如何，本题的空间复杂度是O(N)，时间复杂度是O(N+E)，其中N是任务数，E是依赖关系数。

上一篇 下一篇