题面描述
在一个有依赖关系的任务系统中，任务必须在前置任务完成后才能执行，每个任务需要特定的内存，且内存使用完后会被释放以供其他任务使用。给定任务数量及其内存需求和依赖关系，要求计算系统执行所有任务所需的最小内存。输入数据包括任务数量、各任务的内存需求以及各任务对其他任务的依赖关系矩阵。根据样例输入，系统中有9个任务，分别需要50、50、80、40、40、40、60、60、60的内存，并展示了任务之间的依赖关系。输出为执行所有任务所需的最小内存。
思路: 拓扑排序
一个任务依赖另一个任务表示被依赖的任务是依赖的任务的前置，即如果a[i][j]==1就代表着有一条j指向i的边。如果需要运行时间更小，那么就需要尽量让多的任务并行。那么考虑拓扑排序，每轮将所有入度为0的点的权值求和，即为本轮所消耗的内存。每轮消耗的内存的最大值即为答案。
代码分析
P2369.第3题-内存分配
题目描述
系统由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
~
任务的关系用图表示
|
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
输入
190
