题目描述

假设深度学习模型是一个有向无环图。若算子A依赖算子B的输出，则当B执行完后才能计算A，如果没有依赖关系，则可并行执行，计算每个网络所需要的最短时间。

1. 算子索引从0开始。

题目分析

这一题是有向无环图（多叉树）的遍历问题，给定多叉树信息，求从根节点到叶节点的所有路径中的最大执行时间；

输入输出描述

7
A 10 1 2 3
B 9 4 5 6
C 22 
D 20
E 19
F 18
G 21 

第一行7代表有7个节点，接下来的2～N+1行代表的每一个节点信息；
第一行节点A，消耗时间是10，其子节点为1，2，3（索引从0开始，即代表B、C、D）

将输入转换为多叉树：

邻接矩阵：

输出应该是40。

代码

package com.company;
import java.util.*;
public class Main{
    private static int res = Integer.MIN_VALUE;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //有多少个节点
        int N = sc.nextInt();
        //为了存放回车符
        sc.nextLine();
        //邻接矩阵
        int[][] arr = new int[N][N];
        //各个节点的消耗时间数组，索引从0开始
        int[] a = new int[N];
        //输入每个节点信息
        for(int i=0;i<N;i++){
            //输入如：A 10 1 2 3
            String[] s = sc.nextLine().split(" ");
            //存放索引为i的节点的价值
            a[i]=Integer.parseInt(s[1]);
            //存放当前节点的子节点，放在邻接矩阵中对应位置为1
            if(s.length>2){
                for(int j=2;j<s.length;j++){
                    arr[i][Integer.parseInt(s[j])]=1;
                }
            }
        }
        //邻接矩阵的第0行开始遍历a[0][i]为1的节点，深度遍历以i为起点多路径
        for(int i=1;i<N;i++){
            if(arr[0][i] == 1)
            dfs(arr,a,a[i],N,i);
        }
        System.out.print(a[0]+ res);
    }

    /**
     *
     * @param arr 邻接矩阵
     * @param a  每个节点消耗的时间
     * @param val 当前路径走到第i个节点时消耗的时间
     * @param N  节点个数
     * @param i  当前节点的索引
     * @return
     */
    public static int dfs(int[][] arr, int[] a, int val, int N, int i){
        for(int j=i+1;j<N;j++){
            if(arr[i][j] == 1){
                dfs(arr,a,val+a[j],N,j);
            }
        }
        //以索引i为起点的路径走完，res存放当前最大的消耗时间；
        res = Math.max(res,val);
        return 0;
    }
}

执行结果：