此题解部分借鉴于九野的博客
题目分析
给定一个 \(n\) 个点 \(m\) 条边有向图, 每个点有一个权值, 求一条路径, 使路径经过的点权值之和最大. 你只需要求出这个权值和.
允许多次经过一条边或者一个点, 但是, 重复经过的点, 权值只计算一次.
假如没有后面这条限制的话, 那图一定是一个无环图. 因为有环的话我可以一直在环上跑, 所以答案就没有一个上界
没有环的话我萌可以很自然地想到一个 \(O(n)\) 的 拓扑 \(dp\) 做法, 先做入度为 \(0\) 的点, 更新入度不为 \(0\) 的点, 把更新后入度为 \(0\) 的点加入队列里, 继续做之前的事情
现在考虑有环怎么做
有一个贪心的思路是, 到环上就先把环上的点都走完, 再从环上任意一点出发
其实这个环可以看做一个大点, 也就是我们今天要介绍的主角 \(\to\) 缩点
tarjan 缩点
下面这张图是从 九野的博客 那 copy 过来的
把可以互相抵达的点集叫做一个连通分量
最大的那个可以互相抵达的点点集即为强连通分量
特别的, 单个的点也可以是强连通分量
比如说 :\(\{ 4, 5 \}\) 是一个联通分量, 而 ${4,5,6 } $ 则是一个强连通分量(一个大点)
tarjan 的过程就是通过 dfs 找强连通分量 (大点) 的过程
对图 dfs 一下, 遍历所有未遍历过的点 , 会得到一个有向树, 显然有向树是没有环的.(注意搜过的点不会再搜
则能产生环的 只有 (指向已经遍历过的点) 的边
我们发现 \(7 \to 3\) (红边 / 横叉边)这种边一定不会产生连通分量
而 \(6 \to 4\) (绿边 / 返祖边)这种边一定会产生联通分量
具体来说: 具有父子关系的边一定会产生联通分量
我们在 dfs 的时候需要用一个栈来保存当前所在路径上的点(栈中所有点一定是有父子关系的)
我们用一些数组来表示 dfs 的过程
int tim, dfn[MAX], low[MAX]
\(dfn[i]\) 表示遍历到节点 \(i\) 的时间戳(第几次遍历)
\(low[i]\) 表示往上可以到达最早的点
初始化 \(dfn[i] = low[i] = ++tim\)
我们可以根据上面过程的步骤写出以下代码
- for(int i = head[u]; i; i = nex[i]) {
- if(dfn[to[i]]) {
- if(instack[to[i]]) {
- if(low[to[i]] < low[u]) {
- low[u] = low[to[i]];
- }
- }
- } else {
- dfs(to[i]);
- if(low[to[i]] < low[u]) {}
- low[u] = low[to[i]];
- }
- }
- }
假如当前节点 \(u\), \(dfn[u] == low[u]\) 那就说明栈顶元素一直到节点 \(u\) 都属于一个强联通分量, 感性理解
把栈中元素弹出并且把他们都给标记为同一种颜色(同一个强连通分量)
- if(dfn[u] == low[u]) {
- ++totcol;
- do {
- int v = stk[top];
- col[v] = totcol;
- instack[v] = false;
- } while(stk[top--] != u);
- }
具体实现看代码
\(\color {Deepskyblue} {Code}\) https://www.luogu.com.cn/paste/zkvhftxg
这里还有一道 tarjan 练手好题 https://www.luogu.com.cn/problem/P4611
来源: https://www.cnblogs.com/Lskkkno1/p/11521301.html