Luogu3387【模板】缩点（Kosaraju）

原题链接：https://www.luogu.org/problemnew/show/P3387

【模板】缩点

题目背景

缩点+DP

题目描述

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

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入输出格式

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

输入输出样例

输入样例#1：

2 2
1 1
1 2
2 1

输出样例#1：

2

说明

$n&lt;=10^4,m&lt;=10^5$n<=104,m<=105,点权<=1000

算法：Tarjan缩点+DAGdp

题解

学习一下求$\mathcal{scc}$scc的新姿势$\mathcal{Kosaraju}$Kosaraju。

算法流程：
1.在反向图上$dfs$dfs，返回时将当前点放进栈里。
2.从栈尾倒序$dfs$dfs，每次$dfs$dfs到的点都在一个$scc$scc里。

先考虑下面这个简单有向图：

如果我们从$\mathcal{B}$B部分开始$dfs$dfs，那么每次出来的都是一个$scc$scc，但是从$\mathcal{A}$A开始就会把整张图误判为一个$scc$scc。

如果我们要让每次$dfs$dfs到的恰好构成一个$scc$scc，就要使这个$scc$scc内的点没有指向其他未被遍历过的$scc$scc，如$564132$564132这个顺序。

但这个条件似乎太过苛刻了，只要有一个$\mathcal{B}$B部分的点排在了第一个，我们就能得到正确的答案，所以我们需要第一次$dfs$dfs来搞出反向图的伪拓扑序，按照这个伪拓扑序$dfs$dfs就能得到正确的答案辣！

代码

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5,N=1e4+5;
int val[N],head[M],nxt[M],to[M],sta[N],col[N],dp[N],top,tot,cnt,n,m;
bool vis[N];
vector<int>mmp[M],scc[M];
void add(int f,int t){nxt[++cnt]=head[f],head[f]=cnt,to[cnt]=t;}
void dfs1(int v){int i;for(vis[v]=1,i=head[v];i;i=nxt[i])if(!vis[to[i]])dfs1(to[i]);sta[++top]=v;}
void dfs2(int v){int i;for(vis[v]=1,scc[tot].push_back(v),col[v]=tot,dp[tot]+=val[v],i=mmp[v].size()-1;i>=0;--i)if(!vis[mmp[v][i]])dfs2(mmp[v][i]);}
void dfs3(int v)
{
    if(vis[v])return;
    vis[v]=1;int i,j,mx=0,t;
    for(i=scc[v].size()-1;i>=0;--i)
    for(j=mmp[scc[v][i]].size()-1;j>=0;--j)
    {
        t=col[mmp[scc[v][i]][j]];
        if(t==v)continue;
        if(!vis[t])dfs3(t);
        mx=max(mx,dp[t]);
    }
    dp[v]+=mx;
}
void in()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&val[i]);
    for(int i=1,a,b;i<=m;++i)scanf("%d%d",&a,&b),add(b,a),mmp[a].push_back(b);
}
void ac()
{
    int i,mx=0;
    for(i=1;i<=n;++i)if(!vis[i])dfs1(i);
    memset(vis,0,sizeof(vis));
    for(i=top;i>=1;--i)if(!vis[sta[i]])++tot,dfs2(sta[i]);
    memset(vis,0,sizeof(vis));
    for(i=1;i<=tot;++i)if(!vis[i])dfs3(i);
    for(int i=1;i<=tot;++i)mx=max(mx,dp[i]);
    printf("%d",mx);
}
int main(){in();ac();}