关键活动（pta

#include<iostream>
 
using namespace std;
 
#define N 105
 
int main()
{
    int n,m;     
    int i, j;
    int task1, task2, time;      
    cin >> n >> m;
 
    int graph[N + 1][N + 1];
 
    int dependence[N + 1], re_dependence[N + 1];   //每个点的入度数和出度数
 
    int ae[N + 1], al[N + 1];         //一项活动最先开始的时间 和 一项活动最晚开始的时间
 
    bool vis[N + 1];               //该任务是否已经完成过了
    bool flag = true;              //表示该轮中有任务完成
    int count;                   //当前完成的任务的数量
    int s[N + 1][N + 1];             //表示输入的边的顺序
    int queue[N];              //表示关键路径某个任务中下一个任务编号
    int tail;                    //表示queue中最后一个元素的位置
 
    //初始化
    for (i = 0; i <= n; i++) 
    {
        for (j = 0; j <= n; j++) 
        {
            graph[i][j] = -1;        
            s[i][j] = -1;           
        }
        dependence[i] = 0;
        re_dependence[i] = 0;      
        ae[i] = 0;
        vis[i] = false;
        queue[i] = -1;
    }
 
    //输入
    for (i = 0; i < m; i++) {
        cin >> task1 >> task2 >> time;
        graph[task1][task2] = graph[task2][task1] = time; 
 
        s[task1][task2] = i;             //填入顺序
 
        dependence[task2]++;      //入度     
        re_dependence[task1]++;    //出度
    }
 
    count = 0;
 
    //拓扑排序
    while (flag && count != n) 
    {
        i = 1;
        while (i <= n && (dependence[i] || vis[i]))
            i++;  
        if (i <= n) //存在没有前驱也未被访问过的点
        {
            j = 1;
            while (j <= n)//遍历所有的点
            {
                if (graph[i][j]!=-1 && !vis[j]) //找到和i连通且未被访问
                {
                    dependence[j]--;//删去所有的由i引出的线，入度减1
                    if (ae[j] < ae[i] + graph[i][j])   //选择最长的时间线路
                        ae[j] = ae[i] + graph[i][j];
                } 
                j++;
            }
 
            vis[i] = true;//i点已经被访问过，即i点已经被删除
 
            flag = 1;//该轮中有点被删除，该轮中有任务被完成
 
            count++;//完成的任务数量
 
            if (time < ae[i])
                time = ae[i];     //记录下任务可以完成的最早时间
        }
        else
            flag = 0;
    }
 
    for (i = 0; i <= n; i++) {
        al[i] = time;         //初始化一项任务的最晚开始时间
        vis[i] = false;
    }
 
    count = 0;
 
    while (flag && count != n) {
        i = 1;
        while (i <= n && (re_dependence[i] || vis[i]))
            i++;    //找到依赖的任务都完成并且没有被添加到已完成任务表中的任务
        if (i <= n) {
            j = 1;
            while (j <= n) 
            {
                if (graph[i][j]!= -1   && !vis[j]) {
                    re_dependence[j]--;
                    if (al[j] > al[i] - graph[i][j])   //选择最长的时间线路
                        al[j] = al[i] - graph[i][j];
                }   //说明两个任务之间有依赖关系
                j++;
            }
            vis[i] = true;
            flag = 1;
            count++;
        }
        else
            flag = 0;
    }
 
    if (!flag)
        cout << '0' << endl;
    else 
    {
        cout << time << endl;
        for (i = 1; i <= n; i++) { 
            if (ae[i] != al[i])
                continue;    //说明任务i不在关键路径上
            tail = 0;
            for (j = 1; j <= n; j++) {
                if (-1 != graph[i][j] && ae[j] == al[j] && ae[i] + graph[i][j] == ae[j] && j != i)
                    queue[tail++] = j;
            }              //找到任务i在关键路径上的下一个任务
            int k;
 
            for (j = 0; j < tail; j++)
                for (k = 0; k < tail; k++) {
                    int temp;
                    if (s[i][queue[k]] < s[i][queue[j]])
                    {
                        temp = queue[k];
                        queue[k] = queue[j];
                        queue[j] = temp;
                    }
                }         //冒泡排序 将输入顺序在后的排到前面
            for (j = 0; j < tail; j++)
                printf("%d->%d\n", i, queue[j]);
        }
    }
 
    return 0;
}