@[kirihara233](/user/701221) 你的 top 扔错位置了。
by MarchKid_Joe @ 2022-10-24 14:06:50
@[kirihara233](/user/701221) define int long long 要修改 scanf %lld
by MarchKid_Joe @ 2022-10-24 14:07:54
```cpp
#include<stdio.h>
#define N 100009
#define M 1000009
#define int long long
int head[N], cnt;
struct node
{
int v, nxt;
}e[M];
int val[N], sum[N];
bool vis[N];
int col[N], colcnt;
int dfn[N], low[N], dfncnt;
inline int min(int a, int b) {return a < b ? a : b;}
inline void add(int u, int v)
{
e[++ cnt].v = v, e[cnt].nxt = head[u], head[u] = cnt;
}
int s[N], top;
void tarjan(int u)
{
dfn[u] = low[u] = ++ dfncnt;
vis[u] = 1;
s[++ top] = u;
for (register int i = head[u];i;i = e[i].nxt)
{
int v = e[i].v;
if (!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
++ colcnt;
while (1)
{
int x = s[top];
vis[x] = 0;
col[x] = colcnt;
sum[colcnt] += val[x];
-- top;//swap
if (u == x)//swap
break;
}
}
}
int x[N], y[N];
int dp[N];
inline int max(int a, int b)
{
return a > b ? a : b;
}
int dfs(int u)
{
if (dp[u])
return dp[u];
for (register int i = head[u];i;i = e[i].nxt)
{
int v = e[i].v;
dp[u] = max(dp[u], dp[v]);
}
dp[u] += sum[u];
return dp[u];
}
signed main()
{
register int n, m;
scanf("%lld%lld", &n, &m);
// puts("114514");
for (register int i = 1;i <= n;++ i)
scanf("%lld", &val[i]);
// puts("114514");
for (register int i = 1;i <= m;++ i)
scanf("%lld%lld", &x[i], &y[i]), add(x[i], y[i]);
// puts("114514");
for (register int i = 1;i <= n;++ i)
if (!dfn[i])
tarjan(i);
// puts("114514");
for (register int i = 1;i <= colcnt;++ i)
head[i] = 0;//重构图
for (register int i = 1;i <= m;++ i)
if (col[x[i]] != col[y[i]])//保证没有自环
add(col[x[i]], col[y[i]]);//加边
register int ans = 0;
for (register int i = 1;i <= colcnt;++ i)
ans = max(ans, dfs(i));
printf("%lld", ans);
return 0;
}
```
by MarchKid_Joe @ 2022-10-24 14:08:25
@[MarchKid_Joe](/user/239163) thx
by char_cha_ch @ 2022-10-24 18:48:48