题解：P3387 【模板】缩点

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

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

Part 1 - Tarjan 找 SCC

SCC 是强连通分量。

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

$dfn_u$ ，表示节点 $u$ 是第 $dfn_u$ 个被遍历到的。
$low_u$ ，在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。
栈数组 $st$ ，表示可能构成 SCC 的点的集合。
$vis_u$ ，表示 $u$ 节点是否在栈中。

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

u

。

首先，我们计算

dfn_u

和

low_u

的初始值（

low_u

初始为

dfn_u

）并将

u

节点入栈，

vis_u

自然设为

1

。

随后，我们开始更新

low_u

。我们遍历每个

u

出发的边到达的节点

v

进行如下操作。

如果 $v$ 没被遍历到，那么先 dfs 处理 $v$ ，再将 $low_u= \min(low_u,low_v)$ 。
如果遍历过 $v$ 且 $v$ 在栈中，那 $u,v$ 强连通，就将 $low_u=\min(low_u,dfn_v)$ 。
如果没在栈中，那么 $u$ 和 $v$ 无法形成 SCC。

如果处理完后

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)

。

参考代码

CPP

#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 的题解和这篇本题题解，写得很详细，感谢。

习题巩固

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

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

题解：P3387 【模板】缩点

文章操作

Part 1 - Tarjan 找 SCC

Part 2 - 拓扑排序 & DP

参考代码

致谢

习题巩固

相关推荐

评论

题解：P3387 【模板】缩点