题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include