题解：P3387 【模板】缩点

· · 题解

第一次写模板题题解，如有不足还请指出。

本题解的解法可以拆分为两个部分，即为 tarjan 和拓扑排序。tarjan 先找出所有 SCC，然后把 SCC 缩成一个点，这样就巧妙地把图上的环处理掉了。随后建新图进行拓扑排序和 DP，就解决掉了本题。

Part 1 - Tarjan 找 SCC

SCC 是强连通分量。

对于每个节点，我们需要记录以下几个值：

  3. 栈数组 st，表示可能构成 SCC 的点的集合。

那么现在我们可以开始 tarjan 了，即进行 dfs 处理。令当前节点为 u。

首先，我们计算 dfn_u 和 low_u 的初始值（low_u 初始为 dfn_u）并将 u 节点入栈，vis_u 自然设为 1。

随后，我们开始更新 low_u。我们遍历每个 u 出发的边到达的节点 v 进行如下操作。

如果处理完后 dfn_u=low_u，那说明什么呢？

说明一个 SCC 已经出现了！u 及 u 以下的所有子节点没有边指向 u 前遍历的点，即 u 与它的子孙节点构成了一个 SCC。

得到如此结果，直接弹栈直到把 u 也弹掉即可，把 vis 值全部改为 0。当然，本题要建新图，所以别忘了记录每个点对应的 SCC，这里弹出的点记录为以 u 为代表的 SCC，用 fa 数组表示。同时，我们需要更新 u 节点的权值，即记录以 u 为代表的 SCC 的权值，求和即可。

Part 2 - 拓扑排序 & DP

得到了一张有向无环图后，就可以放心大胆地进行拓扑排序了。注意，起点不能是被缩的点，所以要是入度为 0 且代表一个 SCC 的点。

我们考虑 DP 更新以新图每个节点为终点的路径中的最大权值路径的权值，于是有状态转移方程 dp_v=\max(dp_u+a_v,dp_v)。

最后答案就是 dp 数组中的最大值。

这样，本题结束，时间复杂度为 O(n+m)。因为 SCC 的个数不超过 n，新图边数不超过 m，所以拓扑排序的时间复杂度不超过 tarjan 的 O(n+m)。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m; 
const int N=1e4+10,M=1e5+10; 
vector<int>g[N],ng[N]; 
//ng是新图 
int u[M],v[M],a[N];
int low[N],dfn[N],idx,st[N],top,fa[N];
bool vis[N]; 
int in[N],dp[N]; 

void Tarjan(int u){
    dfn[u]=low[u]=++idx;
    st[++top]=u;
    vis[u]=1; 
    for(int v:g[u]){
        if(!dfn[v]){
            Tarjan(v); 
            low[u]=min(low[u],low[v]);  
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]); 
    }
    if(low[u]==dfn[u]){
        //find SCC! 
        do{ 
            vis[st[top]]=0; 
            fa[st[top]]=u; //标记所属SCC 
            if(u!=st[top])a[u]+=a[st[top]];//更新权值   
        }while(st[top--]!=u);        
    }return;
}

void toposort(){
    queue<int>q; 
    for(int i=1;i<=n;i++){
        if(!in[i]&&i==fa[i]){ //要入度为0且代表SCC 
            q.push(i); 
            dp[i]=a[i]; 
        }
    }
    while(!q.empty()){
        int u=q.front();q.pop(); 
        for(int v:ng[u]){
            dp[v]=max(dp[v],dp[u]+a[v]); 
            if(--in[v]==0){
                q.push(v); 
            }
        }
    }return;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    cin>>n>>m; 
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]; 
        g[u[i]].push_back(v[i]); 
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])Tarjan(i);  
    }//tarjan找SCC
    for(int i=1;i<=m;i++){
        int x=fa[u[i]],y=fa[v[i]]; 
        if(x!=y){
            ng[x].push_back(y); 
            in[y]++; 
        }
    }//建新图
    toposort();//拓扑排序DP
    int ans=0;  
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]); 
    }
    cout<<ans; 
    return 0;
}

致谢

参考了这篇讲解 tarjan 的题解和这篇本题题解，写得很详细，感谢。

习题巩固

  1. P2746 校园网
  2. P2812 校园网加强版
  3. P2002 消息扩散

以上是缩点的习题，tarjan 的习题还有很多。

希望这篇题解能给大家带来帮助。