• 前言
• 题目大意
• 思路
  • tarjan
  • 本题
• 代码
• 总结

前言

链式前向星遍历的时候写成了e[head[i]].nxt，警钟长鸣。

题目大意

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，$0\le a_i\le 10^3$。

思路

很多人在看到了这题的时候以为直接改最短路模版就能水过去，但是结果是在一个环里面不断转悠转悠。

正解是tarjan（好像是废话）。

tarjan

tarjan是一个用来求强联通分量的算法，其实有很多的tarjan，建议说成tarjan求强联通分量算法。这样就不会跟tarjan求割点算法弄混了。

定义一个 $pre$ 数组来装dfs时间戳。然后有一个数组 $low$ 装的是这个点能达到的最小时间戳是多少。之后，如果自己的 $low$ 和 $pre$ 相同，这说明这是一个环的起点，因为它的子树也最低走到 $pre$ 了。之后把这个环标记上即可。

具体怎么求呢？

枚举所有出边，如果 $v$ 还是白点，那么就先递归 $v$，之后 $low[u]=\min(low[u],low[v])$，挺好理解的，子树能到的点自己也能到。黑灰如果 $v$ 还不是一个环上的一部分，那么就用 $pre[v]$ 去更新 $low[u]$，其实这里我还没有太理解，直观上来讲用 $low[v]$ 是正确的，也确实是这样的。但是tarjan用来 $pre[v]$，好像是之后的算法用不了了，留个悬念之后在看吧。

之后等遍历完了所有的边，，那么如果 $pre[u]=low[u]$ 的话就把环标记，可以用栈来做。把所有走过的结点之前都放到栈里了，那么每一次拿一个就是往后导了，最后走到 $u$ 的时候停。

经过了这么多的工作后就求出来了这张图的不同的强联通分量。

本题

由于本题有环，那么就不太能直接跑，那么如果是一个DAG是不是就爽了。我们可以用tarjan找到所有的强联通分量。由于每一个环只能走一次，那如果我们把这个环看成点的话是不是这张图就变成一个DAG了呢？这个点的点权就是环上的所有点权之和。然后在跑一下点权最长路就行了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
struct edge{
    ll from,to,nxt;
}e[MAXN],e1[MAXN];
ll head[MAXN],tot;
void add(ll u,ll v,edge E[]){
    E[++tot].nxt=head[u];
    head[u]=tot;
    E[tot].from=u;
    E[tot].to=v;
}
ll pre[MAXN],low[MAXN],dt,sccNo[MAXN],sccCount,value[MAXN],a[MAXN];
stack<ll>s;
void tarjan(ll u){
    ++dt;
    pre[u]=low[u]=dt;
    s.push(u);
    for (ll i = head[u]; i ; i=e[i].nxt) {
        ll v=e[i].to;
        if(!pre[v]){
            tarjan(v);
            low[u]= min(low[u],low[v]);
        }else if(sccNo[v]==0){
            low[u]= min(low[u],pre[v]);
        }
    }
    if(pre[u]==low[u]){
        sccCount++;
        while (true){
            ll t=s.top();
            s.pop();
            sccNo[t]=sccCount;
            value[sccCount]+=a[t];
            if(t==u){
                break;
            }
        }
    }
    return;
}
ll f[MAXN],ans;
void dfs(ll u,ll Max){
    ans= max(ans,Max);
    for (int i = head[u]; i ; i=e1[i].nxt) {
        dfs(e1[i].to,Max+value[e1[i].to]);
    }
}
ll n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&a[i]);
    }
    for (int i = 1; i <=m ; ++i) {
        ll u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v,e);
    }
    for (int i = 1; i <=n ; ++i) {
        if(pre[i]==0){
            tarjan(i);
        }
    }
    memset(head,0,sizeof(head));
    tot=0;
    for (int i = 1; i <=m ; ++i) {
        if(sccNo[e[i].to]!=sccNo[e[i].from]){
            add(sccNo[e[i].from],sccNo[e[i].to],e1);
        }
    }
    for (int i = 1; i <=sccCount ; ++i) {
        if(!f[i]){
            dfs(i,value[i]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

总结

tarjan是一个求强联通分量的做法，也可以用它去缩点，可以让一个有向有环图变成一个DAG。