#tarjan，樹形dp#洛谷 3387 【模闆】縮點

題目

給定一個 n n n個點 m m 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);
}