题目链接：https://www.luogu.org/problemnew/show/P1113
打眼一看，这不就是道拓扑排序的问题？不过和一般的拓扑排序不同，这里不只是要求一个完成工作的次序，每个工作都有相应的完成所需时间，要求完成所有工作所需的最短时间。之所以这里会有最短时间，是因为已完成准备工作的任务可以同时进行，只要每项工作能完则完，那么最终所有工作都完成所需的时间就是最短的（废话）。还是拓扑排序的思路，只需要这样想，设定一个early数组表示每项工作的最早开始时间，他就等于该工作所有准备工作中，完成最晚的。答案就是整个过程中所经历过最晚的完成时间。
1 #include <cstdio> 2 #include <queue> 3 4 using namespace std; 5 6 inline int get_num() { 7 int num = 0; 8 char c = getchar(); 9 while (c < '0' || c > '9') c = getchar(); 10 while (c >= '0' && c <= '9') 11 num = num * 10 + c - '0', c = getchar(); 12 return num; 13 } 14 15 const int maxn = 1e4 + 5, maxm = 1e6 + 5; 16 17 int head[maxn], eid; 18 19 struct Edge { 20 int v, next; 21 } edge[maxm]; 22 23 inline void insert(int u, int v) { 24 edge[++eid].v = v; 25 edge[eid].next = head[u]; 26 head[u] = eid; 27 } 28 29 int len[maxn], ind[maxn], pre[maxn]; 30 31 queue<int> q; 32 33 int main() { 34 int n = get_num(), ans = 0; 35 for (int i = 1; i <= n; ++i) { 36 get_num(); 37 len[i] = get_num(); 38 int p = get_num(); 39 while (p) { 40 insert(p, i); 41 ++ind[i]; 42 p = get_num(); 43 } 44 } 45 for (int i = 1; i <= n; ++i) 46 if (!ind[i]) q.push(i); 47 while (!q.empty()) { 48 int u = q.front(); 49 q.pop(); 50 for (int p = head[u]; p; p = edge[p].next) { 51 int v = edge[p].v; 52 if (pre[v] < pre[u] + len[u]) 53 pre[v] = pre[u] + len[u]; 54 if (!(--ind[v])) q.push(v); 55 } 56 if (ans < pre[u] + len[u]) ans = pre[u] + len[u]; 57 } 58 printf("%d", ans); 59 return 0; 60 }