【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a454
【解題想法】拓撲排序 (topological sort)
- t[i]：完成第 i 個項目所需的天數。
- out[i]：第 i 個項目的下游項目編號。
- in[i]：第 i 個項目的入邊（上游項目數目）。
- s[i]：有兩種意義
- (Line-36) 真正完成第 i 個項目時，累計花費的時間。
- (Line-39) 每次更新第 i 個項目最早可以開始的時間。
- (Line-37) 每完成一個項目，更新答案。
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int m, n, in[1005], t[1005], s[1005], a, b, c, now, ans;
vector <int> out[1005];
int main() {
cin >> m;
while (m--){
cin >> n;
memset(in, 0, sizeof(in));
memset(t, 0, sizeof(t));
memset(s, 0, sizeof(s));
for (int i = 1; i <= n; i++){
cin >> a;
out[i].clear();
t[i] = a;
cin >> b;
for (int j = 0; j < b; j++){
cin >> c;
in[ c]++;
out[i].push_back(c);
}
}
queue <int> q;
for (int i = 1; i <= n; i++){
if (in[i] == 0) q.push(i);
}
ans = 0;
while (!q.empty()){
now = q.front();
q.pop();
s[now] += t[now];
ans = max(ans, s[now]);
for (auto i:out[now]){
s[i] = max(s[i], s[now]);
in[i]--;
if (in[i] == 0) q.push(i);
}
}
cout << ans << "\n";
}
}