tarjan

一、缩点

题目链接

https://www.luogu.com.cn/problem/P3387

题目大意

题目思路

缩点 + 拓扑序 + dp

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
#define pi pair<int,int>
const int N = 1e4 + 5,M = 1e5 + 5;
using namespace std;
int n,m;
int h[N],ne[M],e[M],idx;
int h1[N],ne1[M],e1[M],idx1;
int stk[N],in_stk[N],top;
int dfn[N],low[N],fa[N],timestamp;
int a[N];
int din[N];
pi edge[M];
int dp[N];
set<pi>s;
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void add1(int a,int b){
    e1[idx1] = b;
    ne1[idx1] = h1[a];
    h1[a] = idx1++;
}
void tarjan(int x){
    dfn[x] = low[x] = ++ timestamp;
    stk[++top] = x;in_stk[x] = 1;
    for(int i = h[x];~i;i = ne[i]){
        int y = e[i];
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }else if(in_stk[y]){
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(dfn[x] == low[x]){
        int y;
        do{
            y = stk[top--];in_stk[y] = 0;
            fa[y] = x;
            if(x == y) break;
            a[x] += a[y];
        }while(true);
    }
}
int topsort(){
    queue<int>q;
    int ans = 0;
    for(int i = 1;i <= n;++i){
        if(fa[i] == i && din[i] == 0){
            q.push(i);
            dp[i] = a[i];
            ans = max(ans,dp[i]);
        }
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h1[u];~i;i = ne1[i]){
            int v = e1[i];
            dp[v] = max(dp[v],dp[u] + a[v]);
            ans = max(ans,dp[v]);
            --din[v];
            if(din[v] == 0) q.push(v);
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    for(int i = 1;i <= m;++i){
        int x,y;scanf("%d%d",&x,&y);add(x,y);
        edge[i] = {x,y};
    }
    for(int i = 1;i <= n;++i){
        if(!dfn[i]) tarjan(i);
    }
    memset(h1,-1,sizeof(h1));
    for(int i = 1;i <= m;++i){
        int x = fa[edge[i].first],y = fa[edge[i].second];
        if(x != y && !s.count({x,y})){
            add1(x,y);
            ++din[y];
            s.insert({x,y});
        }
    }
    printf("%d",topsort());
    return 0;
}