上鏈接：P1113 雜務 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
https://www.luogu.com.cn/problem/P1113
?上題干：
題目描述
John 的農場在給奶牛擠奶前有很多雜務要完成，每一項雜務都需要一定的時間來完成它。比如：他們要將奶牛集合起來，將他們趕進牛棚，為奶牛清洗乳房以及一些其它工作。盡早將所有雜務完成是必要的，因為這樣才有更多時間擠出更多的牛奶。
當然，有些雜務必須在另一些雜務完成的情況下才能進行。比如：只有將奶牛趕進牛棚才能開始為它清洗乳房，還有在未給奶牛清洗乳房之前不能擠奶。我們把這些工作稱為完成本項工作的準備工作。至少有一項雜務不要求有準備工作，這個可以最早著手完成的工作，標記為雜務?11。
John 有需要完成的?n?個雜務的清單，并且這份清單是有一定順序的，雜務 k?(k>1)?的準備工作只可能在雜務?1?至k?1?中。
寫一個程序依次讀入每個雜務的工作說明。計算出所有雜務都被完成的最短時間。當然互相沒有關系的雜務可以同時工作，并且，你可以假定 John 的農場有足夠多的工人來同時完成任意多項任務。
輸入格式
第1行：一個整數n?(3≤n≤10,000)，必須完成的雜務的數目；
第?22?至n+1?行，每行有一些用空格隔開的整數，分別表示：
- 工作序號（保證在輸入文件中是從?1?到?n?有序遞增的）；
- 完成工作所需要的時間 len?(1≤len≤100)；
- 一些必須完成的準備工作，總數不超過?100?個，由一個數字?0?結束。有些雜務沒有需要準備的工作只描述一個單獨的?0。
保證整個輸入文件中不會出現多余的空格。
輸出格式
一個整數，表示完成所有雜務所需的最短時間。
輸入輸出樣例
輸入 #1復制
7 1 5 0 2 2 1 0 3 3 2 0 4 6 1 0 5 1 2 4 0 6 8 2 4 07 4 3 5 6 0輸出 #1復制
23
這道題我們將樣例給的圖在草稿上畫成一個圖就能解決了。
我們由題意可以知道，這種有些任務都有前置條件的情況，所有任務完成的時間，取決于最慢的那個任務。
所以我們只需要找到離1最遠的那個點就可以了，也就是找一根最長的鏈。
所以可以用深度優先遍歷+記憶化，這樣每次搜索到同一個點就不需要再次往下搜索了。
由于是深搜，我們最開始得到的時間必然是最底部的雜物完成所需的時間。
建立一個數組儲存時間，flag[x] ,? ?代表這個點x到底部所需要的時間
再建立一個數組time【x】來儲存每個雜物所需要的時間。
所以現在flag【7】=4，代表從雜物7開始到底部所需要的時間為4
對于上一層的flag? ，需要選擇上一層的分支中最長的那一個，即flag【3】=max( dfs（分支）,flag[3])
遍歷上一層的每一個分支，得到最長的分支，然后再加上本身的時間? flag【3】+=time【3】
這樣的話，3到底部的最長的那一條分支就找到了。
?
接著返回上一層：2
以此類推。
記著在dfs最開始的 地方加一個判斷語句，if（flag【x】）return flag【x】;
目的是記憶化，減少遞歸次數
我們可以得到下面的代碼：
const int N = 1e4 + 10;
int flag[N],times[N];
vector<int > p[N];
int n,ttop;int dfs(int id)
{if (flag[id])return flag[id];for (int i = 0; i < p[id].size(); i++) {flag[id] = max(flag[id], dfs(p[id][i]));}flag[id] += times[id];return flag[id];
}int main()
{cin >> n;int temp = n;while (temp--){int u, v;cin >> u >> times[++ttop];for (; cin >> v;)if (v == 0)break;else p[v].push_back(u);}cout<<dfs(1);
}
