算法
(拓扑排序) $O(n+m)$
本题是 $\operatorname{DAG}$ 上求最长路的板题
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
vector<int> t(n);
rep(i, n) cin >> t[i];
vector<vector<int>> to(n);
vector<int> deg(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
deg[b]++;
}
vector<int> dp(n);
queue<int> q;
rep(i, n) if (deg[i] == 0) dp[i] = t[i], q.push(i);
int ans = 0;
while (q.size()) {
int v = q.front(); q.pop();
chmax(ans, dp[v]);
for (int u : to[v]) {
chmax(dp[u], dp[v]+t[u]);
deg[u]--;
if (deg[u] == 0) q.push(u);
}
}
cout << ans << '\n';
return 0;
}