一 原问题链接

Batch System - HDU 4019 - Virtual Judge

https://vjudge.net/problem/HDU-4019

二 输入和输出

1 输入

输出包括几个测试用例。每个测试用例的第 1 行包含两个整数 N 和 M，表示 N 个指令和 M 个依赖关系。以下 M 行，每行都包含 3 个整数 X、Y、Z，表示 X 和 Y 的安全距离是 Z，Y 在 X 之后运行。指令编号为 0~ N-1。

2 输出

单行输出一个整数，即 CPU 运行所需要的最短时间。

三 输入和输出样例

1 输入

5 2

1 2 1

3 4 1

2 输出

2

四 分析和设计

根据测试用例，构建的图形结构如下图所示。在 1 ns 中，执行指令 0、1和3；在第 2ns 中，执行指令 2 和 4.答案是2。

按照拓扑排序求每个节点的最长距离，然后求各个节点最长距离的最大值。

五 代码

package graph.hdu4109;

import java.util.Scanner;
import java.util.Stack;

public class Hdu4109 {
    static final int maxn = 1005;
    static int map[][];
    static int in[];
    static int topo[] = new int[maxn];
    static int d[] = new int[maxn];
    static int n, m;
    static Stack<Integer> s = new Stack<>();

    static void TopoSort() { // 按拓扑排序求最长距离
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (in[i] == 0) {
                s.push(i);
                d[i] = 1;
            }
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[cnt++] = u;
            for (int v = 0; v < n; v++) {
                if (map[u][v] > 0) {
                    d[v] = Math.max(d[v], d[u] + map[u][v]);
                    if (--in[v] == 0)
                        s.push(v);
                }
            }
        }
    }

    public static void main(String[] args) {
        int u, v, w;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            map = new int[maxn][maxn];
            in = new int[maxn];
            d = new int[maxn];
            for (int i = 1; i <= m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                w = scanner.nextInt();
                map[u][v] = w;
                in[v]++;
            }
            TopoSort();
            int ans = 0;
            for (int i = 0; i < n; i++)
                ans = Math.max(ans, d[i]);
            System.out.println(ans);
        }
    }
}

六 测试

绿色为输入，白色为输出。