ID: 50

Difficulty: 6

题目描述

系统由 $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

输出

解释

第一行: $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$

任务的关系用图表示

				`40`	`60`
				t4	t6
				↑
`50`		`80`	`40`	`60`
t0	t1	t2	t3	t7	t8
		↑
		`40`
		t5

执行 $t0$ ，分配 $m0=50$ ，占用空间 $[0,50)$ ，最大访问地址为 $50$
执行 $t1$ ，分配 $m1=50$ ，占用空间 $[0,50)$ ，最大访问地址为 $50$
并发执行 $t2$ 和 $t5$ ，分配 $m2=80$ ， $m5=40$ ，占用空间 $[0,120)$ ，最大访问地址为120
执行 $t3$ ，分配 $m3=40$ ，占用空间 $[0,40)$ ，最大访问地址 $40$
并发执行 $t4$ 和 $t7$ ，分配 $m4=40$ ， $m7=60$ ，占用空间 $[0,100)$
执行 $t6$ ，分配 $m6=60$ ，占用空间 $[0,60)$ ，最大访问地址 $60$
执行 $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

输入

题面描述

在一个有依赖关系的任务系统中，任务必须在前置任务完成后才能执行，每个任务需要特定的内存，且内存使用完后会被释放以供其他任务使用。给定任务数量及其内存需求和依赖关系，要求计算系统执行所有任务所需的最小内存。输入数据包括任务数量、各任务的内存需求以及各任务对其他任务的依赖关系矩阵。根据样例输入，系统中有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)

#P1551. 2023.08.30-秋招-第三题-内存分配

2023.08.30-秋招-第三题-内存分配