尽管是缩点的习题,思路也是在看了题解后才明白的。
首先,每个强连通分量内的点都是一定互通的,也就是可以完全把这里面的边都跑满,摘掉所有能摘的蘑菇。那么,考虑给每一个强连通分量化为的新点一个点权,代表摘光蘑菇能拿到的边权之和。然后,在新点之间保留原来的桥及其初始权值。(每一个桥一定只能跑一遍,否则说明这两个本应单向通行的分量之间有返回的路径,则二者可构成一个更大的分量。这个结论正是tarjan算法求有向图dcc的核心原理。)现在得到了一张新图,问题在于如何在一张包含点权、边权的DAG上求起始于定点的最长路。首先,每个强连通分量内的点都是一定互通的,