关键活动Java

编程语言：Java
题目：

题解：见注释
结果：AC

import java.io.*;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Scanner sc = new Scanner(new BufferedInputStream(System.in));

    static int[][] graph = new int[105][105];
    static int[] earliest = new int[105];
    static int[] latest = new int[105];
    static int[] indegree = new int[105];
    static int[] outdegree = new int[105];
    static int max = (int) 1e8;

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        //init
        for (int i = 0; i <= n; i++)
            Arrays.fill(graph[i], -1);
        Arrays.fill(latest, max);
        for (int i = 0; i < m; i++) {
            in.nextToken();
            int s = (int) in.nval;
            in.nextToken();
            int e = (int) in.nval;
            in.nextToken();
            int cost = (int) in.nval;
            graph[s][e] = cost;
            indegree[e]++;
            outdegree[s]++;
        }

        Queue<Integer> que = new LinkedBlockingQueue<>();
        int num = 0;
        int time = 0;

        //求事件发生的最早时间
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                que.add(i);
            }
        }
        while (!que.isEmpty()) {
            int p = que.poll();
            //能够进入队列的都是入度为0的结点
            num++;
            for (int i = 1; i <= n; i++) {
                if (graph[p][i] != -1) {
                    //任何事件的最早发生时间都必须大于等于其前置事件的最早发生时间和两事件之间的活动时间之和
                    if(earliest[i]<earliest[p]+graph[p][i]){
                        earliest[i] = earliest[p] + graph[p][i];
                    }
                    //此时已经处理好了该事件的前置事件，可以将该前置事件删除，即入度减一
                    if (--indegree[i] == 0) {
                        que.add(i);
                    }
                    //更新最大的事件最早发生时间，后面需要用来计算事件的最晚发生时间
                    if (earliest[i] > time) {
                        time = earliest[i];
                    }
                }
            }
        }
        if (num == n) {
            out.println(time);
            que.clear();
            //让所有出度为0的事件入列，并且将其最晚发生时间设置为整个工程结束的最早时间，不管有多少个终点，所有终点的最晚发生时间都是工程结束的最早时间
            for (int i = 1; i <= n; i++) {
                if (outdegree[i] == 0) {
                    que.add(i);
                    latest[i] = time;
                }
            }
            while (!que.isEmpty()) {
                int p = que.poll();
                for (int i = 1; i <= n; i++) {
                    if (graph[i][p] != -1) {
                        //任何事件的最晚发生时间都必须小于等于其后置事件的最晚发生时间与两事件之间的活动时间之差
                        if(latest[i]>latest[p]-graph[i][p]){
                            latest[i] = latest[p] - graph[i][p];
                        }
                        if (--outdegree[i] == 0) {
                            que.add(i);
                        }
                    }
                }
            }
            for (int i = 1; i <= n; i++) {
                //如果最早发生时间和最晚发生时间都不一致，说明这个事件的时间可以在一段区间内进行调整，进而也不是关键路径中的一点
                if (earliest[i] != latest[i])
                    continue;
                //在这里之所以要从n开始，是因为当起点相同的时候，需要按照输入任务的相反顺序进行输出
                for (int j = n; j >= 1; j--) {
                    //在这里解释一下两个条件，第一个条件说明两个结点是可连接的
                    // 第二个条件说明，两者的最晚发生时间差就是两者的之间活动花费时间，通俗的说，可以理解成，
                    //  当我完成了第i个事件以及i、j事件之间的活动后，第j个事件也必须马上开始做
                    if (graph[i][j] != -1 &&(latest[j] - latest[i]) == graph[i][j])
                        out.printf("%d->%d\n", i, j);
                }
            }
        } else {
            out.println(0);
        }
        out.flush();
    }
}