题目链接：P1113 杂务 - 洛谷 | 计算机科学教育新生态
题目描述
John 给奶牛挤奶前要完成很多杂务，每一项杂务都需要一些时间来完成，有些杂务必须在另一些杂务完成的情况下才能进行。 比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。这些是准备工作。 至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务 1。John需要完成的 n个杂务，杂务 k (k>1） 的准备工作只可能在杂务 1 至 k−1中，设计一个程序计算最小时间（假设农场工人足够多)
输入格式
第1行：一个整数 n (3≤n≤10,000)，必须完成的杂务的数目；
第 2 至 n+1 行，每行有一些用空格隔开的整数，分别表示：
- 工作序号（保证在输入文件中是从 1 到 n 有序递增的）；
- 完成工作所需要的时间 l和n (1≤l和n≤100)；
- 一些必须完成的准备工作，总数不超过 100 个，由一个数字 0 结束。 有些杂务没有需要准备的工作只描述一个单独的 0。
保证整个输入文件中不会出现多余的空格。
输出格式
一个整数，表示完成所有杂务所需的最短时间。
引入：这是一道拓扑排序的模板题，首先介绍下拓扑排序的概念。拓扑排序是一类用于处理 DAG（Directed acyclic graph），即有向无环图上的问题。
定义：若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
eg：对于下图，1 2 3 就是一个拓扑序列。
可以证明，一个有向无环图，一定有拓扑序列，所以也叫拓扑图。
一个有向无环图一定存在一个入度为 0 的点。
解题思路：以这道题为例，我们分析拓扑排序的作用：
显然地，本题中各项工作是有一定的依赖条件的，也就是说我们在进行工作 X 之前可能需要先进行一些其他的工作 ，而完成工作 X 所需的时间和所有 X 所依赖的工作完成的时间的最大值有关。
在代码实现中，其实是取出队列的队头 t，将 j 的入度减一即可。当一个点的入度减到 0 时，说明所有它的所有前驱已经被计算过了，那么我们将它插入队列。
重复以上步骤，直到队列为空。这时我们就已经统计出了答案。
总结一下，此种拓扑排序共有四个主要步骤：
- 初始化队列，将入度为 0 的节点放入队列。
- 取出队首，遍历其出边，将能够到达的点入度减一，同时维护答案数组。
- 若在此时一个点的入度变为 0，那么将其加入队列。
- 回到第二步，直到队列为空。
最后奉上代码部分：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 1e5 + 10; int n,m;
int h[N], e[N],ne[N], idx;//邻接表存图
queue<int>q;
int d[N],t[N],ans[N];//d入度，t表示时间，ans答案 void add(int a, int b)//建立一条从a指向b的边
{e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}void topsort()//拓扑排序
{while(!q.empty()){int temp = q.front();q.pop();for(int i = h[temp]; i != -1; i = ne[i]){int j = e[i];d[j]--;if(d[j] == 0) q.push(j);ans[j] = max(ans[j],ans[temp] + t[j]);}}
}int read()
{int t = 0, f = 1;char ch = getchar();while(ch > '9' || ch < '0') {if(ch == '-') f = -1;ch = getchar();}while(ch <= '9' && ch >= '0') {t = t * 10 + ch - '0';ch = getchar();}return t * f;
} int main()
{n = read();memset(h, -1, sizeof(h));//一定要初始化 for(int i = 1; i <= n; i++){int u = read();t[i] = read();while(int v = read()) {if(!v) break;add(v,u); d[u] ++;}}for(int i = 1; i <= n; i++)//将度数为0的点插入队列 {if(d[i] == 0) {q.push(i);ans[i] = t[i];}}topsort();int ans1 = 0;for(int i=1; i<=n; i++) ans1 = max(ans[i],ans1);cout<<ans1;return 0;
}
