```cpp
#include <bits/stdc++.h>
#define _FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++(i))
#define _FRO(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define _ROF(i, a, b) for (int (i) = (a); (i) >= (b); --(i))
#define _ORF(i, a, b) for (int (i) = (a); (i) < (b); --(i))
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e4 + 5;
const int maxm = 1e5 + 5;
struct Edge{
int u, v, nxt;
}e[maxm], ed[maxm];
int cnt, head[maxn], d[maxn], tot, n, m, t, sd[maxn], p[maxn];
int dis[maxn], ans, head2[maxn], low[maxn], dfn[maxn];
int s[maxn], top;
bool vis[maxn];
queue<int> q;
// stack<int> s;
void add(int u, int v){
e[++cnt].v = v;
e[cnt].u = u;
e[cnt].nxt = head[u];
head[u] = cnt;
return ;
}
void tarjian(int x){
low[x] = dfn[x] = ++t;
// s.push(x);
s[++top] = x;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt){
int v = e[i].v;
if (!dfn[v]){
tarjian(v);
low[x] = min(low[x], low[v]);
}
else if (vis[v]) low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x]){
int y;
while(y = s[top--]){
sd[y] = x;
vis[y] = 0;
if (x == y) break;
p[x] += p[y];
}
}
return ;
}
void topo(){
_FOR(i, 1, n){
if (sd[i] == i && !d[i]){
q.push(i);
dis[i] = p[i];
}
}
while(!q.empty()){
int x = q.front();
q.pop();
for (int i = head2[x]; i; i = ed[i].nxt){
int y = ed[i].v;
dis[y] = max(dis[y], dis[x] + p[y]);
d[y]--;
if (!d[y]) q.push(y);
}
}
_FOR(i, 1, n) ans = max(ans, dis[i]);
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
_FOR(i, 1, n) cin >> p[i];
_FOR(i, 1, m){
int u, v;
cin >> u >> v;
add(u, v);
}
_FOR(i, 1, n){
if (!dfn[i]) tarjian(i);
}
_FOR(i, 1, m){
int x = sd[e[i].u], y = sd[e[i].v];
if (x == y) continue;
ed[++tot].v = y;
ed[tot].u = x;
ed[tot].nxt = head2[x];
head2[x] = tot;
d[y]++;
}
topo();
cout << ans;
return 0;
}
评价是建图挂了,98、99行的e要改成ed(总不可能在原来的边上继续建吧)
by HugeSB @ 2023-10-13 18:20:13