上海计算机学会 2023年9月月赛 乙组T3 工程建设（拓扑排序）

标签：拓扑排序
题意：有$n$个建设任务，第$i$个建设任务完成时间为$t_i$。给定$m$个前置任务要求，第$j$条规则，若要开工$b_j$号任务，必须先完成$a_j$号任务。所有任务可以并行开工，求最快多少时间完成任务。
题解：拓扑排序模板题，把图建好，入度为$0$的点都扔到队列中，跑图过程中更新一下$u$->$v$，$v$这个顶点的最大时间，要完成所有$v$的前置任务，对该点$v$得求最大值。最终再对每个点求个最大时间就好了。
代码：

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
queue <int> q;
vector<int> e[N];
int t[N], in[N], mx[N];
int n, m, ans = 0;void toposort() {for (int i = 1; i <= n; i++) {if (in[i] == 0) {q.push(i);mx[i] = t[i];}}while (!q.empty()) {int u = q.front();q.pop();for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];in[v]--;if (in[v] == 0) q.push(v);mx[v] = max(mx[v], mx[u] + t[v]);}}for (int i = 1; i <= n; i++) ans = max(ans, mx[i]);
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> t[i];for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;in[b]++;e[a].push_back(b);}toposort();cout << ans << endl;return 0;
}