题解 | 物流网络最优运输路径

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static class Edge {
        int to;
        int profit;

        Edge(int to, int profit) {
            this.to = to;
            this.profit = profit;
        }
    }

    static class Result {
        long profit;
        int lenth;

        Result(long profit, int lenth) {
            this.profit = profit;
            this.lenth = lenth;
        }
    }

    static Map<Integer, List<Edge>> graph = new HashMap<>();

    static Result[] dp = new Result[1000];

    static int[] status = new int[1000];

    static boolean hasCircle = false;

    public static Result dfs(int cur) {
        if (status[cur] == 1) {
            hasCircle = true;
            return new Result(0, 0);
        }

        if (status[cur] == 2) {
            return dp[cur];
        }

        status[cur] = 1;

        long maxProfit = 0;
        int maxLength = 1;

        if (graph.containsKey(cur)) {
            for (Edge edge : graph.get(cur)) {
                Result next = dfs(edge.to);

                long curProfit = edge.profit + next.profit;
                int curLength = 1 + next.lenth;

                if (curProfit > maxProfit ||  (curProfit == maxProfit &&
                                               curLength > maxLength)) {
                    maxLength = curLength;
                    maxProfit = curProfit;
                }

            }
        }


        status[cur] = 2;

        dp[cur] = new Result(maxProfit, maxLength);

        return dp[cur];
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int x = in.nextInt();

        Set<Integer> nodes = new HashSet(1000);

        int[] inDrgree = new int[1000];

        for (int i = 0; i < x; i ++) {
            int cur = in.nextInt();
            int to = in.nextInt();
            int pro = in.nextInt();

            if (graph.get(cur) == null) {
                List<Edge> tmp = new ArrayList<>();
                tmp.add(new Edge(to, pro));
                graph.put(cur, tmp);
            } else {
                List<Edge> tmp = graph.get(cur);
                tmp.add(new Edge(to, pro));
                graph.put(cur, tmp);
            }
            nodes.add(cur);
            nodes.add(to);

            inDrgree[to] += 1;
        }

        long ansProfit = 0;
        int ansLenth = 0;

        for (int node : nodes) {
            if (status[node] == 0) {
                dfs(node);
                if (hasCircle) {
                    System.out.println(-1);
                    return;
                }
            }
        }


        for (int node : nodes) {
            if (inDrgree[node] == 0) {
                Result res = dfs(node);
                if (hasCircle) {
                    System.out.println(-1);
                    return;
                }
                if (res.profit > ansProfit || (res.profit == ansProfit &&
                                               res.lenth > ansLenth)) {
                    ansProfit = res.profit;
                    ansLenth = res.lenth;
                }

            }
        }
        System.out.println(ansProfit + " " + ansLenth);
    }
}

首先制作graph图，用<当前节点数字，List<当前节点指向的节点数字 与 路径利润（Edge类）>>的map类型存储所有节点和节点的指向以及路径利润（Edge类），由于并不清楚总共有多少节点，第一个数字仅代表一共多少行数据，所以使用set类型的nodes，来存储所有不重复的数据，并且存储后能直接通过遍历nodes来遍历所有且仅提供的节点。之后使用status数组记录每个节点被访问的状态，初始状态都是0；1代表正在被访问；2是已经访问结束，且得到了局部最优解存储到dp数组中了，最后记录inDrgree入度数组，inDrgree[to]代表to数字对应的节点有一个入度（0->1【1为to节点，有一个入度来自于0】），之后循环遍历会通过判断这个inDrgree数组来找所有起始点，即入度为0的所有节点。

优先走一遍dfs来判断是否有环路。

判断环路的dfs中，循环判断的是状态status，确保遍历到每一个节点上，如果当前节点的status是1，那就代表当前节点正在被上一层的dfs访问：如果经过了多层dfs之后发现一个已经被访问的，说明出现了环路，用一个全局静态标志hasCircle记录，然后直接返回一个默认值（否则会出现数组越界或者死循环），然后等到回到main函数优先判断hasCircle返回-1。

之后就是正常dp查询，循环判断的是节点入度为0的节点，因为要从头开始，而且肯定没有环，进入一个节点后，首先判断当前节点（cur）状态，如果不是1或者2，那就说明当前节点没被接触到，就先将status[cur]置1，表示当前节点正在被访问中，然后使用一组临时变量记录当前节点的最大利润和能走过的最长路径（因为当前已经是一个节点了，所以路径初始值为1），之后判断graph图中当前节点是否有子节点：

如果没有，直接将状态置为2，说明已经到当前路线的终点了，然后记录当前节点默认的利润（0）以及路线长度（1）（它自己），返回给上一层dfs。

如果有，则通过遍历grapg记录的List<Edge>，找到所有当前节点的x个子节点，然后dfs每一个子节点进入下一层判断，直到走到终点，然后将终点n的默认值（0，1）通过Result类型返回给上一层，之后用循环遍历之外的maxProfit;maxLength对比保存n-1层节点到n层的x个节点中，利润最大的 || （利润相同&&路径最长） 的数据，保存到dp[cur]中，返回给上一层，这样最终dfs返回的就是利润最大的 || （利润相同&&路径最长） 的数据，然后要考虑特殊情况，输出即可。