感觉可以
by liqingyang @ 2023-03-19 21:48:34
```cpp
#include <bits/stdc++.h>
using namespace std;
int m,n,a,cnt=1,ans,low[10001],color[10001],in[10001],dfn[10001],val[10001],last[10001],dp[10001],b,vis[10001];
stack <int> s;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct hh
{
int to;
int next;
int u;
}t[100002],nt[100002];
void tj(int u,int fa)
{
dfn[u]=low[u]=cnt++;
vis[u]=1;
s.push(u);
for(int i=last[u];i;i=t[i].next)
{
int v=t[i].to;
if(!dfn[v])
{
tj(v,u);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
{
low[u]=min(dfn[v],low[u]);
}
}
if(dfn[u]==low[u])
{
while(s.top()!=u)
{
vis[s.top()]=0;
val[u]+=val[s.top()];
color[s.top()]=u;
s.pop();
}
color[u]=u;
vis[s.top()]=0;
s.pop();
}
}
void tp()
{
queue <int> q;
for(int i=1;i<=m;++i)
{
if(color[i]==i&&!in[i])
{
q.push(i);
dp[i]=val[i];
}
}
while(!q.empty())
{
for(int i=last[q.front()];i;i=nt[i].next)
{
int v=nt[i].to,u=nt[i].u;
dp[v]=max(dp[v],val[v]+dp[u]);
in[v]--;
if(!in[v])
{
q.push(v);
}
}
q.pop();
}
for(int i=1;i<=m;++i)
{
ans=max(ans,dp[i]);
}
}
int main()
{
m=read();
n=read();
for(int i=1;i<=m;++i)
{
val[i]=read();
}
for(int i=1;i<=n;++i)
{
a=read();
b=read();
t[cnt]=(hh){b,last[a],a};
last[a]=cnt++;
}
cnt=1;
for(int i=1;i<=m;++i)
{
if(!dfn[i])
{
tj(i,0);
}
}
cnt=1;
memset(last,0,sizeof(last));
for(int i=1;i<=n;++i)
{
int x=color[t[i].u],y=color[t[i].to];//把这个换成x=low[t[i].u],y=low[t[i].to],为什么就不行了,求解
if(x!=y)
{
nt[cnt].to=y;
nt[cnt].next=last[x];
nt[cnt].u=x;
last[x]=cnt++;
in[y]++;
}
}
tp();
cout<<ans;
}
```
by quliannanyishou @ 2023-03-19 21:49:47
@[liqingyang](/user/272088) 我试过了,过不了板子题
by quliannanyishou @ 2023-03-19 21:50:20
想不出hack
by quliannanyishou @ 2023-03-19 21:50:42
把所有用到color的地方都换成了low
听取WA声一片
[wa](https://www.luogu.com.cn/record/105270300)
by quliannanyishou @ 2023-03-19 21:52:53
@[quliannanyishou](/user/682390) 看[这里](https://www.luogu.com.cn/blog/501865/tarjan-graph-algorithms)的图,2 的 dfn 是 5,但它和 1 3 4 是一个强连通分量
by TheSky233 @ 2023-03-19 21:53:50
以及你要的 hack:
```cpp
6 8
1 3
3 5
5 6
4 6
3 4
4 1
1 2
2 4
```
by TheSky233 @ 2023-03-19 21:54:30
@[TheSky233](/user/501865) thx
by quliannanyishou @ 2023-03-19 21:55:18
@[TheSky233](/user/501865) 谢谢
by quliannanyishou @ 2023-03-19 21:55:55