这是一道拓扑排序的模板题
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 最大食物链计数