题目链接：

如果你还不会Tarjan缩点，我建议你还是先看看这篇博客：

或者过一段时间再来

首先我们分析题目，要求出图中的一条路径上点权之和最大的路径的点权之和

那么我们首先可以明确涂上如果有一个环，就一定要走完

或者说有强连通分量的话就要走完，我们便自然而然的想到了割点

最后处理的话就是一个简单的记忆化搜索

下面给出代码:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline int min(int a,int b){ return a
            
             b?a:b;}inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int n,m;int v[100006];int head1[100006],nxt1[200006],to1[200006];int total1=0;void add1(int x,int y){ total1++; to1[total1]=y; nxt1[total1]=head1[x]; head1[x]=total1; return ;}int dfn[100006],low[100006];int color[100006];int tot=0;int color_cnt=0;int book[100006];int sta[100006];int v2[100006];int size=0;void Tarjan(int x,int fa){ //Tarjan模板 low[x]=dfn[x]=++tot; sta[++size]=x; book[x]=1; for(int e=head1[x];e;e=nxt1[e]){ if(!dfn[to1[e]]){ Tarjan(to1[e],x); low[x]=min(low[x],low[to1[e]]); } else if(book[to1[e]]) low[x]=min(low[x],dfn[to1[e]]); } if(dfn[x]==low[x]){ color[x]=++color_cnt; v2[color_cnt]=v[x]; book[x]=0; while(sta[size]!=x){ color[sta[size]]=color_cnt; book[sta[size]]=0; v2[color_cnt]+=v[sta[size]];//这个点的权值的计算，根据题目来确定 size--; } size--; } return ;}int head2[100006],nxt2[200006],to2[200006];int total2=0;void add2(int x,int y){ total2++; to2[total2]=y; nxt2[total2]=head2[x]; head2[x]=total2; return ;}void change(){ for(int i=1;i<=n;i++){ for(int e=head1[i];e;e=nxt1[e]){ if(color[i]!=color[to1[e]]){ add2(color[i],color[to1[e]]);//将两个点连边 } } } return ;}int dis[100006];void dfs(int x){ if(dis[x]) return ; int sum=0; dis[x]=v2[x]; for(int e=head2[x];e;e=nxt2[e]){ if(!dis[to2[e]]) dfs(to2[e]); sum=max(sum,dis[to2[e]]); } dis[x]+=sum; return ;}int main(){ n=rd(),m=rd(); for(int i=1;i<=n;i++) v[i]=rd();//得到点权 for(int i=1;i<=m;i++){ int x=rd(),y=rd(); add1(x,y);//有向边 } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,0); change(); int ans=0; for(int i=1;i<=color_cnt;i++){ if(!dis[i]){ dfs(i); ans=max(ans,dis[i]); } } write(ans); return 0;}