```cpp
#include <bits/stdc++.h>
using namespace std;
const int max_n = 1e4;
const int max_m = 1e5;
//链式前向星
struct edge { int v, next; }edges[max_m];
int tot = -1;
int head[max_n + 1];
//存图
int p[max_n + 1];//点权
int in_degree[max_n + 1];//入度
int n, m, u, v;
//tarjan
int low[max_n + 1];//最早祖先
int dfn[max_n + 1];//访问顺序
int timeclock = 0;//时间戳
int rsp = -1;//栈顶指针
int stack[max_n + 1];//栈
bool in_stack[max_n + 1];//栈内元素
int cnt = 0;
int belong[max_n + 1];//缩点
int new_p[max_n + 1];//new点权
//new链式前向星
edge new_edges[max_m];
int new_tot = -1;
int new_head[max_n + 1];
//topo
queue<int>q;
//dp
int dp[max_n + 1];
int ans = 0;
void add_edge(int u, int v) {
edges[++tot] = { v,head[u] }; head[u] = tot;
}
void new_add_edge(int u, int v) {
new_edges[++new_tot] = { v,new_head[u] }; new_head[u] = new_tot;
}
void topo() {
for (int i = 1; i <= cnt; i++) {//初始化拓扑排序队列
if (in_degree[i] == 0) {
q.push(i);//加入队列
dp[i] = new_p[i];更新到i为止的路径的最大权值和
ans = max(ans, dp[i]);//更新答案
}
}
//拓扑排序
while (!q.empty()) {
int node = q.front();
q.pop();//取出队首
for (int i = new_head[node]; i != -1; i = new_edges[i].next) {//遍历每一条边
int v = new_edges[i].v;
dp[v] = max(dp[v], dp[node] + new_p[v]);更新到v为止的路径的最大权值和
in_degree[v]--;
if (in_degree[v] == 0) {//入度为0
q.push(v);//加入队列
ans = max(ans, dp[v]);//入度为0，dp[v]不再会更新，用其更新答案
}
}
}
}
void tarjan(int node) {
stack[++rsp] = node;
in_stack[node] = true;
dfn[node] = low[node] = ++timeclock;
for (int i = head[node]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (!dfn[v]) {
tarjan(v);
low[node] = min(low[node], low[v]);
}
else if (in_stack[v]) {
low[node] = min(low[node], low[v]);
}
}
if (dfn[node] == low[node]) {
cnt++;
while (stack[rsp + 1] != node) {
belong[stack[rsp]] = cnt;
new_p[cnt] += p[stack[rsp]];
in_stack[stack[rsp--]] = false;
}
}
}
void re_init() {
memset(new_head + 1, -1, sizeof(int) * max_n);
for (int i = 1; i <= n; i++) {
for (int j = head[i]; j != -1; j = edges[j].next) {
int v = edges[j].v;
if (belong[i] != belong[v]) {
new_add_edge(belong[i], belong[v]);
in_degree[belong[v]]++;
}
}
}
}
int main() {
memset(head + 1, -1, sizeof(int) * max_n);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 0; i < m; i++) {
cin >> u >> v;
add_edge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
re_init();
topo();
cout << ans << endl;
return 0;
}
```
by ym_612_04 @ 2024-04-22 18:57:51