题意
给你一张有向图,点有点权,现进行以下操作直到无法进行:
选择两条首尾相连的边 \((a,b)\) 和 \((b,c)\) 且 \(a\) 与 \(c\) 间没边,添加边 \((a,c)\)。
求操作完后图中最长的 不经过重复点的路径,并求这种路径中经过的点的点权和最小值。
思路
先考虑 DAG 上的问题,发现这个操作是无用的:走一条边肯定不如走两条边更优。所以这个操作的作用只有:
-
让一个 SCC 变成完全图。
-
若 \(u\) 和 \(v\) 不在同一 SCC 中且有边,则 \(u\) 所在 SCC 所有点均向 \(v\) 所在 SCC 所有点连边。
换句话说,我们每进入一个 SCC,都可以实现遍历完整个 SCC 并去往其连向的任意 SCC,于是一个 SCC 内的点就不重要了,整个问题就被转化在 DAG 上了,缩点之后遍历一次整个图,每个点从其后继处更新答案就完了。