这是一道拓扑排序的模板题

---

0 额.

所需的前置知识：

• 图论相关的基本概念
• 建图，存图
• 图的遍历
• 非常入门的DP

---

下面进入正文

1 引入

拓扑排序是一类用于处理 DAG（Directed acyclic graph），即有向无环图上的问题。

以这道题为例，我们分析拓扑排序的作用：

显然地，本题中各项工作是有一定的依赖条件的，也就是说我们在进行工作 X 之前可能需要先进行一些其他的工作。

而完成工作 X 所需的时间和所有 X 所依赖的工作完成的时间的最大值有关。（应该还好理解吧）

在这道题中，我们可以列出一个简单的 DP 转移方程：

\[f_i=max\{pre_i\}+a_i
\]

其中\(f_i\)为从最开始到进行完第\(i\)项任务所需的时间，\(pre_i\)为\(i\)号结点的前驱数组，\(a_i\)为做第\(i\)件事所需的时间。

但是，我们如果直接进行dfs遍历，可能会出新一个问题：\(在我们计算f_i的时候，还存在没有计算过的pre_i，从而导致计算结果错误\)

那么，我们在计算的时候，应该确保在计算一个结点\(u\)时，所有与连向它的点都已经被计算过。

而实现这一过程就利用到了今天的主角：拓扑排序（topo sort）

---

锣鼓题解：记忆化搜索。？

此方法可以达到拓扑排序得目的

#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;
int n,x,y,t,ans,len[MAXN],vis[MAXN];
vector<int>e[MAXN];
int miHoYo(int x){
    if(vis[x])  return vis[x];//如果被访问过，直接返回
    for(int i=0;i<e[x].size();i++)// 循环：x每条边指向的点
        vis[x]=max(vis[x],miHoYo(e[x][i]));// 动态规划，求最大值
    vis[x]+=len[x];//加上所需要的时间，构成动态规划公式
    return vis[x];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>len[i];
        while(cin>>y)
            if(!y)  break;
            else e[y].push_back(x);
    }
    for(int i=1;i<=n;i++)//对于每个点进行dfs求f得最大值
        ans=max(ans,miHoYo(i));//   取最大值
    cout<<ans;
    return 0;
}

拓扑排序代码拷自Keith_2006

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>

#define ll long long

using namespace std;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N=500005;

int ind[N],f[N],a[N];  //ind--入度   f--答案   a--时间
vector <int> edge[N];
queue <int> q;

int main() {
    int n=read();
    for (int i=1;i<=n;i++) {
        int x=read();
        a[i]=read();
        while (int y=read()) {
            if (!y) break;
            edge[y].push_back(x);
            ind[x]++;
        }
    }
    //步骤一
    for (int i=1;i<=n;i++) {
        if (ind[i]==0) {
            q.push(i);
            f[i]=a[i];
        }
    };
    while (!q.empty()) {
        int rhs=q.front();
        q.pop();
        //步骤二
        for (int i=0;i<edge[rhs].size();i++) {
            int u=edge[rhs][i];
            ind[u]--;
            if (ind[u]==0) q.push(u);  //步骤三
            f[u]=max(f[u],f[rhs]+a[u]);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans=max(ans,f[i]);   //统计答案
    }
    printf("%d\n",ans);
    return 0;
}

拓扑排序详细讲述见P4017 最大食物链计数