图9 关键活动

题目：https://pintia.cn/problem-sets/1268384564738605056/problems/1286606445168746498
题解：https://blog.csdn.net/qq_38996065/article/details/79919366
代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define inf 999999
using namespace std;
struct vertex{
    int earliest;
    int latest;
}v[105]; 
struct node{
    int x,y,rank;
    friend bool operator < (node a, node b)
    {
        if(a.x==b.x)
        {
            return a.rank<b.rank;
        }
        else    return a.x>b.x;
    }
}np,na;
 
queue<int>q;
priority_queue<node>q2;
int c[105][105],d[105][105],In[105] = {0},Out[105] = {0};
 
int main()
{
    int n,m,a,b,t,i,j,x,cnt = 0,max = 0,flag = 0;
    scanf("%d %d",&n,&m);
    for(i = 1; i <= 105; i++)
    {
        v[i].earliest = 0;
        v[i].latest = inf;
    }
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j<= n; j++)
        {
            c[i][j] = inf;
        }
    }
    for(i = 0; i < m; i++)
    {
        scanf("%d %d %d",&a,&b,&t);
        c[a][b] = t;
        np.x = a;
        np.y = b;
        np.rank = ++cnt;
        q2.push(np);
        In[b]++;
        Out[a]++;
    }
    cnt = 0;
    for(i = 1; i <= n; i++)
    {
        if(In[i]==0)
        {
            v[i].earliest = 0;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        cnt++;
        if(v[x].earliest>=max)
        {
            max = v[x].earliest;
        }
        for(i = 1; i <= n; i++)
        {
            if(c[x][i]!=inf)
            {
                if(v[i].earliest<=v[x].earliest+c[x][i])
                {
                    v[i].earliest = v[x].earliest+c[x][i];
                }
                if(--In[i]==0)
                {
                    q.push(i);
                }
            }
        }
    }
    if(cnt!=n)    printf("0
");
    else
    {
        flag = 1;
        printf("%d
",max);
    }
    if(flag)
    {
        for(i = 1; i <= n; i++)
        {
            if(Out[i]==0)
            {
                v[i].latest = max;
                q.push(i);
            }
        }
        while(!q.empty())
        {
            x = q.front();
            q.pop();
            for(i = 1; i <= n; i++)
            {
                if(c[i][x]!=inf)
                {
                    if(v[i].latest >= v[x].latest-c[i][x])
                    {
                        v[i].latest = v[x].latest-c[i][x];
                    }
                    if(--Out[i]==0)    q.push(i);
                }
            }
        }
        while(!q2.empty())
        {
            na = q2.top();
            d[na.x][na.y] = v[na.y].latest-v[na.x].earliest-c[na.x][na.y];
            if(d[na.x][na.y]==0)
            {
                printf("%d->%d
",na.x,na.y);
            }
            q2.pop();
        }
    }
}