```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5;
vector<int> G[maxn];
vector<int> E[maxn];
int n,m,T,ssc[maxn],dfn[maxn],low[maxn],st[maxn],top,w[maxn];
bool instk[maxn];
void dfs(int u){
dfn[u]=low[u]=++T;
st[++top]=u; instk[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(instk[v]){
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u]){
int y;
while (y=st[top--])
{
ssc[y]=u;
instk[y]=0;
if (u==y) break;
w[u]+=w[y];
}
}
}
queue<int> Q;
int in[maxn],ans,dp[maxn];
void topo(){
for(int i=1;i<=n;i++){
if(ssc[i]==i && in[i]==0) Q.push(i),dp[i]=w[i];
}
while(!Q.empty()){
int u=Q.front(); Q.pop();
//cout<<u<<endl;
for(int i=0;i<E[u].size();++i){
int v=E[u][i];
in[v]--;
if(!in[v]) Q.push(v);
dp[v]=max(dp[v],dp[u]+w[v]);
}
}
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1,a,b;i<=m;++i){
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
for(int i=1;i<=n;i++){
for(int j=0;j<G[i].size();++j){
int t=G[i][j];
if(ssc[i]!=ssc[t]){
E[i].push_back(t); in[t]++;
}
}
}
topo();
return 0;
}
```
by Zlylovecoding @ 2021-11-19 20:41:50
@[Zlylovecoding](/user/370121) Tarjan更新错了吧
by _Int_ @ 2021-11-19 20:47:54
@[Zlylovecoding](/user/370121) 有两个错误,第一个是缩点的时候 `else if(instk[v]) low [u]=min(low[u],dfn[v])` , 第二个是
```c++
if(ssc[i]!=ssc[t]){
E[i].push_back(t);in[t]++;
}
```
需要改成
```c++
if(ssc[i]!=ssc[t]){
E[ssc[i]].push_back(ssc[t]);in[ssc[t]]++;
}
```
by YksKuusiTAlv @ 2021-11-19 20:48:39
第二个用dfn更新
by _Int_ @ 2021-11-19 20:48:52
附上改Ac后的代码
```c++
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5;
vector<int> G[maxn];
vector<int> E[maxn];
int n,m,T,ssc[maxn],dfn[maxn],low[maxn],st[maxn],top,w[maxn];
bool instk[maxn];
void dfs(int u){
dfn[u]=low[u]=++T;
st[++top]=u; instk[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(instk[v]){
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u]){
int y;
while (y=st[top--])
{
ssc[y]=u;
instk[y]=0;
if (u==y) break;
w[u]+=w[y];
}
}
}
queue<int> Q;
int in[maxn],ans,dp[maxn];
void topo(){
for(int i=1;i<=n;i++){
if(ssc[i]==i && in[i]==0) Q.push(i),dp[i]=w[i];
}
while(!Q.empty()){
int u=Q.front(); Q.pop();
//cout<<u<<endl;
for(int i=0;i<E[u].size();++i){
int v=E[u][i];
in[v]--;
if(!in[v]) Q.push(v);
dp[v]=max(dp[v],dp[u]+w[v]);
}
}
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1,a,b;i<=m;++i){
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
for(int i=1;i<=n;i++){
for(int j=0;j<G[i].size();++j){
int t=G[i][j];
if(ssc[i]!=ssc[t]){
E[ssc[i]].push_back(ssc[t]); in[ssc[t]]++;
}
}
}
topo();
return 0;
}
```
by YksKuusiTAlv @ 2021-11-19 20:49:16
突然就慌了,为什么我忽然感觉自己所有的算法+数据结构忘得一干二静
赶紧从A+B学起啊
by _farawaystar_ @ 2021-11-19 21:04:45
噢噢噢!谢谢大家%%%祝各位rp++
by Zlylovecoding @ 2021-11-19 21:14:17