#tarjan，树形dp#洛谷 3387 【模板】缩点

本文主要是介绍#tarjan，树形dp#洛谷 3387 【模板】缩点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

分析

那么这道题首先要把环缩点，然后在有向无环图跑一遍dp，但是tarjan还是很难理解

代码

#include <cstdio>
#include <cctype>
#include <stack>
#include <cstring>
#define rr register
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=10001;
struct node{int x,y,next;}e[N*10];
stack<int>stac; bool v[N];
int dfn[N],low[N],ls[N],n,c[N],sag[N],a[N],f[N],m,cnt,k=1,num,ans;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void tarjan(int x){dfn[x]=low[x]=++num;stac.push(x); v[x]=1;for (rr int i=ls[x];i;i=e[i].next)if (!dfn[e[i].y]){tarjan(e[i].y);low[x]=min(low[x],low[e[i].y]);}else if (v[e[i].y])low[x]=min(low[x],dfn[e[i].y]);if (dfn[x]==low[x]){++cnt; rr int y;do{y=stac.top(); stac.pop();v[y]=0; c[y]=cnt; sag[cnt]+=a[y];}while (x!=y);}
}
inline void dfs(int x){f[x]=sag[x];rr int ans=0;for (rr int i=ls[x];i;i=e[i].next){if (!f[e[i].y]) dfs(e[i].y);ans=max(ans,f[e[i].y]);}f[x]+=ans;
}
signed main(){n=iut(); m=iut();for (rr int i=1;i<=n;++i) a[i]=iut();for (rr int i=1;i<=m;++i){rr int x=iut(),y=iut();e[++k]=(node){x,y,ls[x]}; ls[x]=k;}for (rr int i=1;i<=n;++i)if (!dfn[i]) tarjan(i);memset(ls,0,sizeof(ls)); m=k; k=1;for (rr int i=2;i<=m;++i)if (c[e[i].x]!=c[e[i].y])e[++k]=(node){c[e[i].x],c[e[i].y],ls[c[e[i].x]]},ls[c[e[i].x]]=k;for  (rr int i=1;i<=cnt;++i)if (!f[i]) dfs(i),ans=max(ans,f[i]);return !printf("%d",ans);
}