题面描述

在一个有依赖关系的任务系统中，任务必须在前置任务完成后才能执行，每个任务需要特定的内存，且内存使用完后会被释放以供其他任务使用。给定任务数量及其内存需求和依赖关系，要求计算系统执行所有任务所需的最小内存。输入数据包括任务数量、各任务的内存需求以及各任务对其他任务的依赖关系矩阵。根据样例输入，系统中有9个任务，分别需要50、50、80、40、40、40、60、60、60的内存，并展示了任务之间的依赖关系。输出为执行所有任务所需的最小内存。

思路: 拓扑排序

一个任务依赖另一个任务表示被依赖的任务是依赖的任务的前置，即如果$a[i][j] == 1$就代表着有一条j指向i的边。如果需要运行时间更小，那么就需要尽量让多的任务并行。那么考虑拓扑排序，每轮将所有入度为0的点的权值求和，即为本轮所消耗的内存。每轮消耗的内存的最大值即为答案。

代码分析

这段代码实现了基于拓扑排序的任务调度算法，用于计算执行所有任务所需的最小内存。以下是简要分析：

1. 数据结构

• int in[M]: 存储每个任务的入度（依赖于该任务的其他任务数）。
• int a[M]: 存储每个任务所需的内存大小。
• vector<int> e[M]: 邻接表表示任务间的依赖关系。

2. 输入处理

• 读取任务数量 n 和每个任务的内存需求。
• 构建依赖关系矩阵，更新入度数组和邻接表。

3. 拓扑排序实现

• 使用队列 q 存储当前入度为0的任务。
• 每轮处理队列中的任务，累加内存消耗，并更新依赖任务的入度。
• 将入度减至0的任务加入临时队列 tmp。

4. 更新最大内存消耗

• 每轮结束后，更新记录的最大内存消耗 ans。

5. 输出结果

• 输出最终的最大内存消耗，即执行所有任务所需的最小内存。

代码

C++

#include <bits/stdc++.h>

using namespace std;

#define ll long long // 定义长整型
#define pii pair<int, int> // 定义一个整数对
#define pb push_back // 简化向容器添加元素的操作

const int M = 605; // 定义最大任务数量
int in[M], a[M]; // in数组存储每个任务的入度，a数组存储每个任务的内存需求
vector<int> e[M]; // 使用邻接表表示依赖关系图

int main() {
    int n, t; // n表示任务数量，t用于读取依赖关系
    cin >> n; // 输入任务数量
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i); // 输入每个任务的内存需求
    }
    // 读取任务间的依赖关系
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &t);
            if (t) {
                in[i]++; // 增加任务i的入度
                e[j].pb(i); // 记录有一条从任务j到任务i的依赖边
            }
        }
    }
    
    queue<int> q, tmp; // q保存当前入度为0的任务，tmp用于保存下一轮的任务
    // 将所有入度为0的任务加入队列
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) q.push(i); // 加入初始任务
    }
    
    int ans = 0; // 用于记录最大内存消耗
    while (!q.empty()) { // 当队列不为空时，说明还有可执行的任务
        int sum = 0; // 当前轮次内存消耗总和
        while (!q.empty()) { // 处理当前轮次所有入度为0的任务
            int u = q.front(); // 获取队头任务
            q.pop(); // 从队列中移除该任务
            sum += a[u]; // 累加内存消耗
            // 遍历所有依赖于任务u的任务
            for (int i = 0; i < (int)e[u].size(); i++) {
                in[e[u][i]]--; // 将依赖于u的任务的入度减1
                if (in[e[u][i]] == 0) tmp.push(e[u][i]); // 如果入度为0，将其加入tmp队列
            }
        }
        ans = max(ans, sum); // 更新最大内存消耗
        // 将下一轮的所有入度为0的任务加入队列
        while (!tmp.empty()) {
            q.push(tmp.front());
            tmp.pop();
        }
    }
    cout << ans << endl; // 输出最终的最大内存消耗
    return 0; // 结束程序
}

java

import java.util.*;

public class Main {
    static final int M = 20;
    static int[] in = new int[M];
    static int[] a = new int[M];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer>[] e = new ArrayList[M];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            e[i] = new ArrayList<>();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int t = scanner.nextInt();
                if (t != 0) {
                    in[i]++; // 拓扑排序入度++
                    e[j].add(i);  // 表示有一条j到i的边
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        Queue<Integer> tmp = new LinkedList<>(); // tmp保存本轮产生的所有入度为0的点，q表示已经入度为零的点
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                q.add(i); // 加入初始点
            }
        }

        int ans = 0;
        while (!q.isEmpty()) {
            int sum = 0;
            while (!q.isEmpty()) {
                int u = q.poll();
                sum += a[u];  // 本轮所有点消耗求和
                for (int i = 0; i < e[u].size(); i++) {
                    int v = e[u].get(i);
                    in[v]--;
                    if (in[v] == 0) {
                        tmp.add(v); 
                    }
                }
            }
            ans = Math.max(ans, sum);
            q.addAll(tmp);// 下一轮的点
            tmp.clear();
        }

        System.out.println(ans);
    }
}

python

from collections import deque

M = 605
in_degree = [0] * M
a = [0] * M
e = [[] for _ in range(M)]

n = int(input())
a[1:n+1] = map(int, input().split())

for i in range(1, n+1):
    row = list(map(int, input().split()))
    for j in range(1, n+1):
        if row[j-1]:
            in_degree[i] += 1 # 拓扑排序入度++
            e[j].append(i) # 表示有一条j到i的边

q = deque()
tmp = deque() # tmp保存本轮产生的所有入度为0的点，q表示已经入度为零的点

for i in range(1, n+1):
    if in_degree[i] == 0:
        q.append(i) # 加入初始点

ans = 0

while q:
    total_sum = 0
    while q:
        u = q.popleft()
        total_sum += a[u]  # 本轮所有点消耗求和
        for v in e[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                tmp.append(v)
    ans = max(ans, total_sum)
    q.extend(tmp) # 下一轮的点
    tmp.clear()

print(ans)

题目描述

系统由$n$个任务组成，任务运行有依赖关系，前序任务执行完毕才可以启动后续任务。任务在启动前申请内存，执行完毕后释放，内存释放后可用于其他任务使用。解除依赖后的任务会直接由操作系统调度，分配内存，进入运行状态。每个任务的运行时间相等。请计算系统所有任务执行所需要的最小内存。

输入

第$1$行为$1$个正整数$n$，表示任务个数，$n<20$

第$2$行为$n$个正整数，表示每个任务所需要的内存大小，$0<内存<1000$

第$3$行为$n$个取值为$0$或$1$的数，表示任务$0$对其他任务的依赖关系，$0$表示不依赖，$1$表示依赖

....

第$3+n$行为$n$个取值为$0$或$1$的数，表示任务$n-1$对其他任务的依赖关系，$0$表示不依赖，$1$表示依赖

输出

输出系统任务执行所需要的最小内存

样例

输入

9
50 50 80 40 40 40 60 60 60
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0

输出

120

解释

第一行:$9$，表示有$9$个任务 第二行: $50$ $50$ $80$ $40$ $40$ $40$ $60$ $60$ $60$，表示任务$t0~08$需要的内存大小

第三行:$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t$不依赖任务其他任务 第四行:$10$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t1$依赖$t0$

第五行:$01$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t2$依赖$t1$

~

任务的关系用图表示

1. 执行$t0$，分配$m0=50$，占用空间$[0,50)$，最大访问地址为$50$
2. 执行$t1$，分配$m1=50$，占用空间$[0,50)$，最大访问地址为$50$
3. 并发执行$t2$和$t5$，分配$m2=80$，$m5=40$，占用空间$[0,120)$，最大访问地址为120
4. 执行$t3$，分配$m3=40$，占用空间$[0,40)$，最大访问地址$40$
5. 并发执行$t4$和$t7$，分配$m4=40$，$m7=60$，占用空间$[0,100)$
6. 执行$t6$，分配$m6=60$，占用空间$[0,60)$，最大访问地址$60$
7. 执行$t8$，分配$m8=60$，占用空间$[0,60)$，最大访问地址$60$

输出系统的需要的最小内存为$120$

样例2

输入

10
40 50 80 10 30 80 90 30 70 150
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

输入

190