Aimee

tarjan是一个好东西

如果这个题没有环，那很简单

讨厌环

那就缩点，毕竟说了一个边只算一次

tarjan找到强联通分量，然后缩成一个点

怎么做呢？

有一个dfn，也就是时间戳，还有一个low，表示能向下到达的最小的时间戳

然后dfssssssssssssssssssssssssssssssssssssssssssssssss

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
using namespace std;
struct b{
    int to;
    int ne;
}e[100005][2];
int n,m;
stack <int> s;
int p;
int Aimee[10005];
int head[10005][2];
void add(int f,int to,int con){
    p++;
    e[p][con].ne=head[f][con];
    e[p][con].to=to;
    head[f][con]=p;
    return ;
}
int x,y;
int tim;
int num[10005];
int dfn[10005],low[10005];
int sim[10005];
int Archie;
void dfs(int now){
    tim++;
    dfn[now]=low[now]=tim;
    s.push(now);
    for(int i=head[now][0];i;i=e[i][0].ne){
        int v=e[i][0].to;
        if(!dfn[v]){//没遍历过 
            dfs(v);
            low[now]=min(low[now],low[v]);
        }else if(num[v]==0){//还没有被标记，虽然被遍历过了 
            low[now]=min(low[now],dfn[v]);
        }
    }
    if(dfn[now]==low[now]){//这就是一个点啊 
        Archie++;
        while(1){
            x=s.top();
            s.pop();
            sim[Archie]+=Aimee[x];
            num[x]=Archie;
            if(x==now)break;
        }
    }
}
int dp[10005];
void dfss(int now){
    if(dp[now]) return ;
    dp[now]=max(dp[now],sim[now]);
    for(int i=head[now][1];i;i=e[i][1].ne){
        int v=e[i][1].to;
        dfss(v);
        dp[now]=max(dp[now],dp[v]+sim[now]);
    }
}
int forever;
int main(){
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;++i){
        scanf("%d",&Aimee[i]);
    } 
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(x,y,0); 
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i])
        dfs(i);
    }
    p=0;
    for(int i=1;i<=n;++i){
        for(int j=head[i][0];j;j=e[j][0].ne){
            x=e[j][0].to;
            if(num[x]!=num[i]){
                add(num[i],num[x],1);
            }
        }
    }
    for(int i=1;i<=Archie;++i){
        dfss(i);
    }
    for(int i=1;i<=Archie;++i){
        forever=max(forever,dp[i]);
    }
    cout<<forever;
    return 0;
}