小翟抄论文_牛客博客

小翟为了完成一篇论文，一共要抄袭n篇文章。其中第i篇文章需要a[i]的时间去完成。小翟可以发动粉丝同时抄袭多篇文章，但存在一些文章，只有当它的若干个前置文章抄袭完成后，才能开始抄袭该文章。同时我们认为小翟和其粉丝在一篇文章的前置文章都完成后，能马上开始抄袭该文章。为了让小翟尽快完成论文,获得博士学位，在最优的情况下，小翟的论文什么时候可以完成？
小翟虽然不知道知网，但是他想知道在保证论文尽快完成的情况下（即保证上题答案不变情况），每篇文章最早什么时候可以开始抄袭，和最晚什么时候可以开始抄袭。设第i篇文章最早可以抄袭的时间为f[i];在不影响论文完成时间前提下，第i篇文章最晚可以抄袭的时间为g[i]. 请你回答∏i=0-n (g[i]-f[i]+10) 除以10^9+7所得的余数,题目保证有解。
输入：
第一行输入一个整数n，m
第二行输入n个正整数，a1，a2，…，an描述每篇文章抄袭所需要的时间。
接下来读入m行，每行读入两个整数u，v，表示编号为u的文章是编号为v文章的前置文章
所有的输入数据都满足1<=n<=5*10^5，1<=m<=10^6，1<=a[i]<=10^6
输出：
第一行输出一个整数表示论文最早完成时间。
第二行输出一个整数表示∏i=0-n (g[i]-f[i]+10) 除以10^9+7所得的余数
样例输入：
8 9
11 17 16 20 14 12 13 15
1 3
2 4
4 3
3 6
5 6
2 5
6 8
5 7
7 8
样例输出：
80
459599979
备注：
∏i=0-n 为i从0到n的累乘符号

题目描述：就是拓扑排序的题但问题不同解法也发生了很大改变题目要找出每件工作最早和最晚完成的时间；

分析：因为是无环图，所以直接用dfs跑第一次到达的一定是最早的时间（多次出现取最大（拓扑排序的精髓）），并且可以找出总共工作完成的时间ans，再用ans从尾开始跑一边，取最小这就是最迟完成的时间

#include<bits/stdc++.h>
using namespace std;
const int MAX=5e5+5;
const int mod=1e9+7;
vector<int> mapp[MAX];
vector<int >mapp1[MAX];
int f[MAX],g[MAX];
int value[MAX];
int n,m;
long long  ans=0;
int vis[MAX],vis1[MAX];
void dfs(int x){
    for(int i=0,sz=mapp[x].size();i<sz;i++){
        int v=mapp[x][i];
        if(f[v]<f[x]+value[v]) f[v]=f[x]+value[v];
        if(f[v]>ans) ans=f[v];
        dfs(v);
    }
}
void dfs1(int x){
    for(int i=0,sz=mapp1[x].size();i<sz;i++){
        int v=mapp1[x][i];
        if(g[v]>g[x]-value[x]) g[v]=g[x]-value[x];
        dfs1(v);
    }
}
int main(){
//    freopen("1.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>value[i];
    value[0]=0;
    memset(vis,0,sizeof(vis));
    memset(vis1,0,sizeof(vis1));
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        mapp[x].push_back(y);
        mapp1[y].push_back(x);
        vis[y]=1;
        vis1[x]=1;
    }
    memset(f,0,sizeof(f));
    memset(g,0x3f3f3f3f,sizeof(g));
    for(int i=1;i<=n;i++)
        if(!vis[i]) mapp[0].push_back(i);
    for(int i=1;i<=n;i++)
        if(!vis1[i]){
            mapp1[0].push_back(i);
        }
    dfs(0);
    g[0]=ans;
    dfs1(0);
    cout<<ans<<endl;
    ans=1;
    for(int i=1;i<=n;i++)
        ans=(ans*(g[i]-f[i]+10))%mod;
    cout<<ans<<endl;
}