RT

有人Wa过第一个点吗...

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10004 , MAXM = 200005;
int start[MAXN],cnt = 0,n,m;
int dfn[MAXN],low[MAXN],top = 0 , now = 0 , z = 0 , tack[MAXN],vis[MAXN],color[MAXN],siz[MAXN];
int dp[MAXN],val[MAXN];
int locked[MAXN];
map <pair<int,int>,int > mp;

struct Edge {
    int next,to,from;
} edge[MAXN],New[MAXM];

void add(int from,int to)
{
    cnt ++;
    edge[cnt].to = to;
    edge[cnt].next = start[from];
    start[from] = cnt;
    edge[cnt].from = from;
    return ;
}

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++now;
    top ++ , tack[top] = x , vis[x] = 1;
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[x] = min(low[x],low[to]);
        }
        else if(vis[to]) low[x] = min(low[x],dfn[to]);
    }
    if(dfn[x] == low[x])
    {
        z ++;
        while(tack[top + 1] != x)
        {
            color[tack[top]] = z;
            vis[tack[top]] = 0;
            siz[z] += val[tack[top]];
            top --;
        }
    }
    return ;
}

void topo()
{
    queue <int> q;
    for(int i = 1 ; i <= z ; i ++)
        if(locked[i] == 0) q.push(i),dp[i] = siz[i];
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = start[x] ; i ; i = edge[i].next)
        {
            int to = edge[i].to;
            locked[to] --;
            dp[to] = max(dp[to],dp[x] + siz[to]);
            if(locked[to] == 0)q.push(to);
        }
    }
}

int main()
{
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++)
        val[i] = read();
    for(int i = 1 ; i <= m ; i ++)
    {
        int u = read() , v = read();
        add(u,v);
    }
    for(int i = 1 ; i <= n ; i ++)
    if(!dfn[i])tarjan(i);
    cnt = 0;
    memset(start,0,sizeof(start));
    for(int i = 1 ; i <= m ; i ++)
    {
        if(color[edge[i].to] == color[edge[i].from])continue;
        if(!mp[make_pair(edge[i].from,edge[i].to)])
        {
            add(color[edge[i].from] , color[edge[i].to]);
            locked[color[edge[i].to]] ++;
            mp[make_pair(edge[i].from,edge[i].to)] = 1;
        }
    }
    topo();
    int M = -1100;
    for(int i = 1 ; i <= z ; i ++)M = max(M,dp[i]);
    cout << M;
    return 0;
}