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