为啥我 MAXN=1e4+7,MAXM=1e5+7 会re8个点
但是乘了十之后就过了
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7, MAXM = 1e6 + 7;
struct Node {
int nxt, to;
}Edge[MAXM];
int H[MAXN], E_cnt;
void add(int from, int to) {
Edge[++ E_cnt] = Node{H[from], to};
H[from] = E_cnt;
}
int n, m, Value[MAXN];
int Dfn[MAXN], Low[MAXN], Scc[MAXN], scc, cnt;
bool V[MAXN];
int Sum[MAXN];
stack <int> T;
void tarjan(int u) {
Dfn[u] = ++ cnt; Low[u] = Dfn[u];
V[u] = true; T.push(u);
for (int i = H[u]; i; i = Edge[i].nxt) {
int v = Edge[i].to;
if (!Dfn[v]) tarjan(v), Low[u] = min(Low[u], Low[v]);
else if (V[v]) Low[u] = min(Low[u], Low[v]);
}
if (Dfn[u] == Low[u]) {
Scc[u] = ++ scc; Sum[scc] = Value[u];
while (!T.empty() && T.top() != u) V[T.top()] = 0, Scc[T.top()] = scc, Sum[scc] += Value[T.top()], T.pop();
T.pop(); V[u] = 0;
}
}
int X[MAXN], Y[MAXN], In[MAXN], ans, Dp[MAXN];
int topu() {
queue <int> Q;
for (int i = 1; i <= scc; i ++) {
if (!In[i]) Q.push(i);
}
while (!Q.empty()) {
int now = Q.front(); Q.pop();
Dp[now] += Sum[now];
for (int i = H[now]; i; i = Edge[i].nxt) {
int v = Edge[i].to;
Dp[v] = max(Dp[v], Dp[now]);
if (-- In[v] == 0) Q.push(v);
}
ans = max(ans, Dp[now]);
}
return ans;
}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> Value[i];
for (int i = 1; i <= m; i ++) {
cin >> X[i] >> Y[i]; add(X[i], Y[i]);
}
for (int i = 1; i <= n; i ++)
if (!Dfn[i]) tarjan(i);
memset(H, 0, sizeof(H)); E_cnt = 0;
for (int i = 1; i <= m; i ++) {
int x = Scc[X[i]], y = Scc[Y[i]];
if (x == y) continue;
add(x, y); In[y] ++;
}
cout << topu();
return 0;
}