做过的原题，模拟赛时 PDF 里的题面实在有点难受。
首先有显然结论：在一个环上反走一定是不值的，因为环上的点本来就相互可达。
所以考虑缩点。缩点后的问题可以看成：求对于每一个点 \(x\)，遍历所有能到达他的点 \(from\)，求 \(1\) 到 \(x\) 的最长路以及 \(from\) 到 \(1\) 的最长路的和，减去 \(1\) 所在 SCC 的体积（因为被算了两次，去一次，回来一次）的最小值。
对于缩点后的图建立正图与反图，分别处理最短路。问题解决。
这里再提供一下公式化的描述：设正图最短路数组为 \(dis1\)，反图最短路数组为 \(dis2\)，对于每个点能到达他的点存储在数组 \(from\) 中，大小统一写为 \(siz\)，\(1\) 点连通块的体积为 \(S\)。
答案即为：
\[\max\limits_{i=1}^n(dis1_i + \max\limits_{j=1}^{siz} dis2_j-S) \] 标签：缩点,dis1,题解,短路,数组,P3119,Grass,Cownoisseur From： https://www.cnblogs.com/victoryang-not-found/p/17090565.html