缩点算法学习笔记

缩点
说说缩点，缩点可以算是强连通分量的一个小小的进阶。
本博客也可以理解为 P3387 【模板】缩点 - 传送门 的题解。
正片开始——

一 题目分析
求有向图上的一条路径，使该路径上点的权值和最大，输出和的最大值（可以重复经过点和边）。
啊当然了，你可以使用 spfa 或者 dijkstra 以 ac 这道题，这里说说缩点的方法。
首先，对于任何一个强连通分量里面，我们可以拿到所有的权值，所以我们将所有 的强连通分量缩成一个个“超级点”，最后找到一条类似链的路径使这条“链”的权值最大。
缩点，是我们在解决强连通分量的题目时可以大大简化该题的工具。
二 缩点操作
这题我们来真真正正地“物理缩点”。
在最初建边时把每一条边的 (u, v) 都存下来； 清空关于前向星的数组结构体变量； 遍历每一条边，若该边的初始点和终点不在同一强连通分量中，就建该边；
以上就是缩点操作了，很简单

缩点算法学习笔记最先出现在Python成神之路。