from collections import defaultdict,deque
N = int(input())
time = list(map(int,input().split()))
edges = defaultdict(list)
indeg = [0]*N
for i in range(N):
    data = list(map(int,input().split()))
    if len(data)==1 and data[0]==-1:
        continue
    else:
        for j in range(len(data)):
            edges[i].append(data[j]-1)
            indeg[data[j]-1]+=1

q = deque([u for u in range(N) if indeg[u]==0])
dt = time[:]
while q:
    u = q.popleft()
    for v in edges[u]:
        indeg[v]-=1
        dt[v]=max(dt[v],dt[u]+time[v])
        if indeg[v] == 0:
            q.append(v)
print(max(dt))

带缓存的DFS解法，相比拓扑排序解法更容易理解一点。一个任务的完成所需要的时间未dist[i]=max(dist[j])+value[i]，j为任务i所依赖的任务集合。如果j依赖其他任务，继续递归计算完成其前置任务所需要的时间。将这个结果缓存起来可以减少DFS重复递归。

#include <bits/stdc++.h>
#include <fstream>
using namespace std;

int dfs(vector<int> &rtimes, vector<vector<int>> &rqtask, vector<int> &cache_time, int id) {
    int pretime = 0;
    if(cache_time[id] != -1)
        return cache_time[id];
    for(int pre_id : rqtask[id])
        pretime = max(pretime, dfs(rtimes, rqtask, cache_time, pre_id));
    cache_time[id] = rtimes[id] + pretime;
    return cache_time[id];
}


int main() {
    int n, tmp;
    string str;
    cin >> n;
    vector<int> rtimes(n);
    vector<vector<int>> rqtask(n);
    vector<int> cache_time(n, -1);
    for(int i=0; i<n; ++i) {
        cin >> rtimes[i];
    }
    cin.ignore();
    for(int i=0; i<n; ++i) {
        getline(cin, str);
        istringstream ss(str);
        while(ss >> tmp) {
            if(tmp != -1)
                rqtask[i].push_back(tmp-1); // 我们id从0开始计算
        }
    }
    int ans = 0;
    for(int i=0; i<n; ++i) {
        ans = max(ans, dfs(rtimes, rqtask, cache_time, i));
    }
    printf("%d\n", ans);
    return 0;
}

题面解释:

题目要求开发一个自动化部署调度程序，软件安装分为多个步骤，某些步骤有依赖关系，必须先完成前置步骤才能执行后续步骤，且无依赖的步骤可以并行执行。输入包括步骤总数、每个步骤所需的时间以及每个步骤的依赖关系，输出为完成所有步骤的最短时间。例如，输入步骤总数为4，每个步骤的执行时间为6, 2, 1, 2，依赖关系为某些步骤没有依赖，某些步骤有依赖，输出最短完成时间为9。

思路:拓扑排序(BFS)

该问题本质是有向无环图（DAG）中的拓扑排序问题，要求根据步骤依赖关系调度任务，计算并行执行的最短完成时间。

通过拓扑排序，使用队列依次处理无依赖的节点，更新后续步骤的最早开始时间，累积计算每个步骤完成的最短总时间，最后输出最大值。

更新的方式为:$dist[i] = max(dist[j]) + value[i]$ , 这里的j是i的前驱节点。

解题思路

1. 拓扑排序的定义

拓扑排序是一种用于对有向无环图（DAG）进行排序的方法，它将顶点按照依赖关系排成一个线性序列，使得对图中的每条边 $(u,v)$，顶点 $u$ 在 $v$ 之前出现。

在本题中，每个步骤可以视为一个顶点，步骤之间的依赖关系可以视为有向边。如果步骤 $A$ 依赖于步骤 $B$，则可以表示为一条从 $B$ 到 $A$ 的有向边。

2. 拓扑排序解决方案

我们通过拓扑排序来模拟步骤的执行过程，核心思想是从那些没有依赖的步骤（即入度为 0 的节点）开始，依次执行，同时更新其他步骤的最早完成时间。

具体步骤如下：

1. 读取输入数据：首先读取任务数量、每个任务的执行时间，以及任务的依赖关系。
2. 构建依赖关系图：使用邻接表存储每个步骤的依赖关系，同时使用入度数组记录每个步骤的入度（即有多少前置步骤未完成）。
3. 初始化队列：将所有入度为 0 的任务（没有前置依赖的步骤）放入队列中，它们可以立即开始执行。
4. 拓扑排序处理：从队列中依次取出当前可以执行的任务，并更新后续任务的最早完成时间。如果某个任务的所有前置步骤都已经完成，则将其加入队列。
5. 计算总时间：在遍历图的过程中，维护一个全局的最大完成时间变量，最终即为完成所有任务的最短时间。

3. 状态更新公式

在拓扑排序过程中，使用动态规划的思想更新每个步骤的最早完成时间。对于每一个步骤 $i$，我们通过以下公式更新其完成时间： [ \text{completionTime}[i] = \max(\text{completionTime}[j]) + \text{taskTime}[i] ] 其中，$j$ 是步骤 $i$ 的所有前驱任务，$\text{taskTime}[i]$ 是步骤 $i$ 所需的执行时间。这个公式保证了每个步骤只有在所有前置依赖完成之后才能开始执行。

复杂度分析

• 时间复杂度：构建邻接表和入度数组的时间复杂度为 $O(N + E)$，其中 $N$ 是任务数量，$E$ 是依赖关系的数量。拓扑排序的时间复杂度也是 $O(N + E)$，因此总体时间复杂度为 $O(N + E)$。
• 空间复杂度：空间复杂度为 $O(N + E)$，用于存储邻接表、入度数组和任务时间等信息。

具体细节见代码注释

代码

python

# 读取输入
n = int(input())  # 任务数量
time_costs = [0] + list(map(int, input().split()))  # 每个任务的时间
edge = [[] for _ in range(n + 1)]  # 构建邻接表
in_degree = [0] * (n + 1)  # 记录每个节点的入度

# 读取依赖关系
for i in range(1, n + 1):
    tmp = list(map(int, input().split()))  # 读取每个任务的依赖
    if tmp[0] == -1:  # 如果没有依赖任务
        continue
    for u in tmp:
        edge[i].append(u)  # 将依赖任务加入邻接表
        in_degree[u] += 1  # 更新依赖任务的入度

# 拓扑排序的函数
def top_sort(start_nodes):
    q = []  # 队列，存储入度为0的节点
    dist = [-1 for _ in range(n + 1)]  # 存储每个任务的最短完成时间

    # 初始化入度为0的节点
    for start_node in start_nodes:
        q.append(start_node)
        dist[start_node] = time_costs[start_node]

    while q:
        u = q.pop(0)  # 取出队列中的一个任务
        for v in edge[u]:  # 遍历其依赖的后续任务
            in_degree[v] -= 1  # 更新依赖任务的入度
            if in_degree[v] == 0:  # 当入度变为0时，加入队列
                q.append(v)
            # 更新后续任务的最早完成时间
            if dist[v] == -1 or dist[v] < dist[u] + time_costs[v]:
                dist[v] = dist[u] + time_costs[v]
    return max(dist)  # 返回最晚完成时间

# 找出所有入度为0的任务
start_nodes = [i for i in range(1, n + 1) if in_degree[i] == 0]
print(top_sort(start_nodes))  # 输出任务调度的最短完成时间

C++

#include <iostream> // 引入输入输出流库
#include <vector>   // 引入向量库
#include <queue>    // 引入队列库
#include <string>   // 引入字符串库
#include <sstream>  // 引入字符串流库

using namespace std;

int main(){
    int taskCount; // 任务数量
    cin >> taskCount; // 从输入中读取任务数量
    
    // 定义任务所需时间数组（从索引 1 开始）
    vector<int> taskTime(taskCount + 1);
    
    // 定义入度数组，用于记录每个任务的依赖关系数量（初始为 0）
    vector<int> inDegrees(taskCount + 1, 0);
    
    // 从输入中读取每个任务所需的时间
    for (int i = 1; i <= taskCount; i++){
        cin >> taskTime[i];
    }
    
    cin.ignore(); // 忽略换行符
    
    // 定义依赖关系数组，dep[i] 代表任务 i 的所有后继任务
    vector<vector<int>> dependencies(taskCount + 1);
    
    // 读取每个任务的依赖信息
    for (int i = 1; i <= taskCount; i++){
        string dependencyLine;
        getline(cin, dependencyLine); // 读取每行的依赖关系
        istringstream dependencyStream(dependencyLine); // 使用字符串流处理输入
        
        int prerequisiteTask; // 存储依赖任务编号
        while (dependencyStream >> prerequisiteTask){
            if (prerequisiteTask != -1){ // 如果输入的任务编号不为 -1
                dependencies[prerequisiteTask].push_back(i); // 添加后继任务 i 到任务 prerequisiteTask 的依赖列表中
                inDegrees[i]++; // 任务 i 的入度加 1
            }
        }
    }

    // 定义队列用于拓扑排序，存储所有没有前置依赖的任务（即入度为 0 的任务）
    queue<int> zeroInDegreeQueue;

    // 定义一个数组 `completionTime`，用于记录每个任务的最早完成时间
    vector<int> completionTime(taskCount + 1, 0);

    // 找出所有初始的没有依赖的任务，加入队列，并将其完成时间设置为其所需时间
    for (int i = 1; i <= taskCount; i++){
        if (inDegrees[i] == 0){
            zeroInDegreeQueue.push(i); // 入度为 0 的任务加入队列
            completionTime[i] = taskTime[i]; // 初始化其完成时间
        }
    }

    int totalTime = 0; // 定义结果变量，存储所有任务的最早完成时间

    // 拓扑排序，处理队列中的每个任务
    while (!zeroInDegreeQueue.empty()){
        int currentTask = zeroInDegreeQueue.front(); 
        zeroInDegreeQueue.pop(); // 从队列中取出一个当前任务

        // 更新结果时间，记录最长的任务完成时间
        totalTime = max(totalTime, completionTime[currentTask]);

        // 遍历当前任务的所有后继任务
        for (int nextTask : dependencies[currentTask]){
            // 更新后继任务的完成时间（当前任务的完成时间 + 后继任务所需时间）
            completionTime[nextTask] = max(completionTime[nextTask], completionTime[currentTask] + taskTime[nextTask]); 
            
            // 当前后继任务的前置依赖完成数减 1
            if (--inDegrees[nextTask] == 0){
                zeroInDegreeQueue.push(nextTask); // 如果后继任务没有前置依赖了，加入队列
            }
        }
    }

    cout << totalTime; // 输出所有任务的最早完成时间
    return 0;
}

Java

import java.util.*;

class Main {
    // 记录每个步骤被谁依赖
    static List<Integer>[] relations;
    static int[] inDegree;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] stepTime = new int[n + 1]; // 每个步骤的执行时间
        relations = new List[n + 1]; // 每个步骤依赖的其他步骤
        inDegree = new int[n + 1]; // 每个步骤的入度，即依赖它的步骤数

        // 初始化列表
        for (int i = 1; i <= n; i++) {
            relations[i] = new ArrayList<>();
        }

        // 读取步骤执行时间
        for (int i = 1; i <= n; i++) {
            stepTime[i] = sc.nextInt();
        }

        sc.nextLine();

        // 读取依赖关系
        for (int i = 1; i <= n; i++) {
            String[] str = sc.nextLine().split(" ");
            for (String s : str) {
                int k = Integer.parseInt(s);
                if (k == -1) {
                    break; // -1表示没有依赖
                } else {
                    relations[k].add(i); // k步骤完成后才能进行i步骤
                    inDegree[i]++; // i步骤依赖k步骤，入度加1
                }
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        int[] earliestCompletionTime = new int[n + 1]; // 记录每个步骤的最早完成时间

        // 初始化：将所有入度为0的步骤加入队列
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                earliestCompletionTime[i] = stepTime[i]; // 初始完成时间为自身执行时间
            }
        }

        int res = 0;

        // 拓扑排序，处理每个步骤的完成时间
        while (!queue.isEmpty()) {
            int k = queue.poll();

            // 更新最终的最早完成时间
            res = Math.max(res, earliestCompletionTime[k]);

            // 处理依赖于步骤k的其他步骤
            for (int relation : relations[k]) {
                inDegree[relation]--;
                // 更新依赖步骤的完成时间
                earliestCompletionTime[relation] = Math.max(earliestCompletionTime[relation], earliestCompletionTime[k] + stepTime[relation]);
                if (inDegree[relation] == 0) {
                    queue.offer(relation);
                }
            }
        }

        // 输出结果：所有步骤中的最大完成时间
        System.out.print(res);
    }
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。