题目描述

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

输入

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

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

题面描述

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

思路: 拓扑排序

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

代码分析