Speedrun

· · 题解

又是一道赛后两分钟敲完的题。

\text{Link}

题意

你有 n 个任务，第 i 个任务完成的时间可以设定为 xk+h_i(x\in[0,\infty))，同时有 m 个限制，要求第 a_i 个任务完成的时间不超过第 b_i 个任务完成的时间，且这种单向关系不会形成环（保证 a_i<b_i）。

求完成时间最晚与最早的任务的时间差的最小值。

分析

把题中的 m 条限制当做有向边，那么这就是个有向无环图。

有一个贪心的想法是让每个任务完成的时间尽量靠前，于是我们可以在 \text{DAG} 上 \text{dp}，记 dep_u 表示第 u 个任务的系数 x 的最小值，那么对于 v 的每条入边 u\rightarrow v，有：

dep_v=\max_{u\rightarrow v\in E}\{dep_u+[h_u>h_v]\}

答案为 \max_{i=1}^n\{dep_ik+h_i\}-\min_{i=1}^n\{dep_ik+h_i\}。

但是这样是错的，样例告诉我们，可以通过把完成时间最小的几个点的 dep 值 +1 来减小答案。显然，选择 +1 的点只可能是入度为 0 的点，选择其他点只会得不偿失，于是可以枚举选择的断点，改变那几个点的初始 dep，再重新拓扑排序。

可这样的时间复杂度仍高达 O(n^2)，考虑优化。可以发现，先选择一个点后，产生的变化都形如“如果 dep_i 可以 +1，那么它对 i 在 \text{DAG} 上的后继以及本身影响后的最大值”，故我们将该值设为 ch_i，有：

ch_u=\max\{(dep_u+1)k+h_u,\max_{u\rightarrow v\in E}\{ch_v\times[dep_u+[h_u>h_v]+1>dep_v]\}\}

于是 ch 可以通过记忆化搜索求出，最终可求出答案。

代码

虽然题目给的就是拓扑序，但我还是用了拓扑排序

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=2e5+10;
int t,n,m,k;
ll h[N],dep[N];
int head[N],ver[N],nxt[N],tot,in[N];
void add(int x,int y){
    ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;in[y]++;
}
queue<int>q;
void topu(){
    while(q.size())q.pop();
    for(int i=1;i<=n;i++){
        if(!in[i])
            q.push(i),dep[i]=0;
    }
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            dep[y]=max(dep[y],dep[x]+(h[x]>h[y]));
            in[y]--;
            if(!in[y])
                q.push(y);
        }
    }
}
int a[N],top;
ll ch[N];
bool cmp(int x,int y){
    return h[x]<h[y];
}
ll dfs(int x){
    if(ch[x]!=-1)return ch[x];
    ch[x]=(dep[x]+1)*k+h[x];
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(dep[x]+(h[x]>h[y])+1>dep[y])
            ch[x]=max(ch[x],dfs(y));
    }
    return ch[x];
}
int main(){
    t=read();
    while(t--){
        n=read();m=read();k=read();
        for(int i=1;i<=n;i++){
            h[i]=read();in[i]=head[i]=dep[i]=0;
            ch[i]=-1;
        }
        tot=top=0;
        for(int i=1;i<=m;i++){
            int x=read(),y=read();
            add(x,y);
        }
        for(int i=1;i<=n;i++)
            if(!in[i])a[++top]=i;
        sort(a+1,a+top+1,cmp);
        topu();
        ll mx=0,ans=1e18;
        for(int i=1;i<=n;i++)
            mx=max(mx,dep[i]*k+h[i]);
        for(int i=1;i<=n;i++)dfs(i);
        for(int i=1;i<=top;i++){
            ans=min(ans,mx-h[a[i]]);
            mx=max(mx,ch[a[i]]);
        }
        write(ans);puts("");
    }
    return 0;
}