Milk Scheduling S——拓扑排序

农民约翰有N头奶牛(1<=N<=10,000)，编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于FJ的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。
为了尽量完成挤奶任务，FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。

输入格式
第 1 行：两个空格分隔的整数：N（奶牛数量）和 M（挤奶约束数量;1 <= M <= 50,000）。
第 2..1+N 行：第 i+1 行包含 T(i) 的值 （1 <= T(i) <= 100,000）。
第 2+N 到1+N+M 行：每行包含两个空格分隔的整数 A 和 B，表示奶牛 A 必须完全挤奶，然后才能开始给奶牛 B 挤奶。这些限制永远不会形成循环，因此解决方案总是可能的。

输出格式
挤奶所有奶牛所需的最短时间。

输入样例：
3 1 
10 
5 
6 
3 2

输出样例：
11

解析：

提到先后顺序，就不难想到拓扑排序。值得注意的是，虽然这道题问的是总时间的最小值，但我们要求的是这张图的最长路。下面我们来证明一下：
首先要明确的是，题目给定的图不一定连通（样例就具有这个性质）,因此我们就要把它分成多个部分。
接着可以得出两个结论：每个部分之间是相互独立的，用题目的话说就是可以同时挤奶；每个部分内部是相互约束的，必须要等前面的奶牛挤完后再挤下一只。
最后，我们设每个部分的用时为 t1 ,t2 ,...,tk ，不难得出总用时为 max{t1 ,t2 ,...,tk}，即为原图最长路。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
typedef pair<int,int> PII;
const int N=2e6+10;
vector <int> g[N];
int d[N],t[N],w[N];
int n,m;
queue <int> q;
signed main()
{
    ios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>t[i];
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        d[b]++;
    }
    for (int i=1;i<=n;i++)
    {
        if (!d[i]) 
        {
            q.push(i);
            w[i]=t[i];
        }
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for (auto x:g[u])
        {
            w[x]=max(w[x],w[u]+t[x]);
            d[x]--;
            if (!d[x]) q.push(x);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,w[i]);
    cout<<ans;
    return 0;
}