题面描述

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

思路: 拓扑排序

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

代码分析

题目描述

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