传送门

 

题意：给你一个有向图，找寻一条路径使得经过的权值和最大（点可以重复经过，但是权值只加一次，点上的权值可加可不加）。

思路：用tanjar缩点将图转化为DAG，在tanjar缩点过程中记录一个强连通分量中正权值和，然后再跑一边记忆化dfs即可。

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const ll mod=998424353;
const double INF=1e15;
const int maxn=1e5+5;

int n,m;
int value[30005];

struct node
{
    int e;
    int p;
}load[150005];
int sign,head[30005];

vector<int>p[30005];
int dp[30005];

int cnt,top,time;
int dfn[30005],low[30005];
int stack_[30005],instack[30005],belong[30005];

int sum[30005];

void add_edge(int s,int e)
{
    load[++sign]=node{e,head[s]};
    head[s]=sign;
}

void init()
{
    time=cnt=top=sign=0;
    for(int i=0;i<=n;i++)
    {
        dfn[i]=low[i]=sum[i]=instack[i]=0;
        head[i]=-1;
        dp[i]=-1;
        p[i].clear();
    }
}

void tanjar(int s)
{
    dfn[s]=low[s]=++time;
    instack[s]=1;
    stack_[++top]=s;
    for(int i=head[s];i!=-1;i=load[i].p)
    {
        int e=load[i].e;
        if(!dfn[e])
        {
            tanjar(e);
            low[s]=min(low[s],low[e]);
        }
        else
        {
            if(instack[e])
                low[s]=min(low[s],dfn[e]);
        }
    }
    int t;
    if(dfn[s]==low[s])
    {
        cnt++;
        do
        {
            t=stack_[top--];
            instack[t]=0;
            belong[t]=cnt;
            if(value[t]>0)///只取正值
                sum[cnt]+=value[t];
        }while(t!=s);
    }
}

int dfs(int s)
{
    if(dp[s]!=-1)
        return dp[s];
    dp[s]=sum[s];
    int d=p[s].size(),e;
    for(int i=0;i<d;i++)
    {
        e=p[s][i];
        dp[s]=max(dp[s],dp[e]+sum[s]);
    }
    return dp[s];
}

int main()
{
    int s,e;
    while(~scanf("%d %d",&n,&m))
    {
        init();
        for(int i=0;i<n;i++)
            scanf("%d",&value[i]);
        while(m--)
        {
            scanf("%d %d",&s,&e);
            add_edge(s,e);
        }
        for(int i=0;i<n;i++)
        {
            if(!dfn[i])
                tanjar(i);
        }
        ///将缩点后的图重新建边
        for(int i=0;i<n;i++)
        {
            for(int j=head[i];j!=-1;j=load[j].p)
            {
                e=load[j].e;
                if(belong[i]!=belong[e])
                    p[belong[i]].push_back(belong[e]);
            }
        }
        int ans=0;
        for(int i=1;i<=cnt;i++)
            ans=max(ans,dfs(i));
        printf("%d\n",ans);
    }
    return 0;
}