题意
给出具有依赖关系的 \(n\) 个任务，每个任务只能在某一天的第 \(h_i\) 小时做。只要满足了依赖关系，一个小时可以做很多任务。求最小的完成时间。
分析
结合题目条件，很快发现这是一个有多个联通块的 DAG。
拆分一下问题，先考虑怎么求单个联通块的所有开始时间和结束时间，然后再合并起来。
对于结束时间，发现可以通过简单的 DP 得到。需要注意的是，要保证后做的任务时间大于等于先做的，为了达到这一点，每次增加的只会是整天的时间。
对于开始时间，可以对所有入度为零的点取 \(\max\)。
显然，如果把某些联通块的开始结束时间整体后推一天是有可能取到更优的值的。而且，一个块最多被推后一天。
所以就考虑枚举一个一天中的开始时间，并把小于的块开始结束时间整体后移。
但是，这样还是有问题的（WA 无数次的惨痛教训）。因为如果在某个块里还有一个更晚的开始时间，有可能结束时间根本就不会变动；更为恶心的是，由于这是一个 DAG，所以会有多个出度为零的点，它们当中可能有些点增加了，而另一些没有变动。
观察最初算时间的 DAG 上 DP 过程，发现如果一个入度非零的点 \(u\) 需要增加一天，前提是它的前驱 \(l\) 满足 \(f_l+k>f_u\)。
因此，再细分一下，对于每一个出度为 \(0\) 的点 \(i\)，都去维护一个 \(st_i\)，表示会使 \(i\) 增加一天的入度为 \(0\) 的点中最小的开始时间，可以简单证明一定有这样的点。这样一来就可以按照前面的思路正确讨论了。
一个实现上的小细节：求 \(st\) 数组的过程中可以在反图上进行记忆化搜索，很明显这是可以递推。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+10;
const ll inf=1e18;
int n,m,rd[N],tot;
ll f[N],k,suf[N],mn[N];
vector<int>G[N],G1[N];
struct node{
ll x,y;
}b[N];
inline bool cmp(node x,node y){
return x.x<y.x;
}
inline ll dfs(int u){
if(mn[u]<inf) return mn[u];
if(!G1[u].size()) return mn[u]=f[u];
for(int v:G1[u]){
if(f[u]-f[v]<k) mn[u]=min(mn[u],dfs(v));
}
return mn[u];
}
inline void topsort(){
queue<int>q;
for(int i=1;i<=n;++i){
if(!rd[i]){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int v:G[u]){
--rd[v];
if(!rd[v]) q.push(v);
if(f[u]>f[v]){
f[v]+=(f[u]-f[v]+k-1)/k*k;
}
}
}
for(int i=1;i<=n;++i){
if(G[i].empty()){
b[++tot]={dfs(i),f[i]};
}
}
}
int main(){
memset(mn,0x3f,sizeof mn);
int T;
scanf("%d",&T);
while(T--){
tot=0;
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;++i){
scanf("%lld",&f[i]);
}
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
++rd[y];
G[x].push_back(y);
G1[y].push_back(x);
}
topsort();
sort(b+1,b+1+tot,cmp);
for(int i=tot;i>=1;--i){
suf[i]=max(suf[i+1],b[i].y);
}
ll mx=0,ans=9e18;
int j=1;
for(int i=1;i<=tot;){
while(j<i){
mx=max(mx,b[j].y+k);
++j;
}
ans=min(ans,max(suf[i],mx)-b[i].x);
int tmp=b[i].x;
while(i<=tot&&b[i].x==tmp) ++i;
}
printf("%lld\n",ans);
for(int i=1;i<=n;++i){
G[i].clear();
G1[i].clear();
rd[i]=suf[i]=0;
mn[i]=inf;
}
}
return 0;
}