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;
}