P1781记录

很有意思的题目，巨佬ljt赛时切了，在这里记录一下思路。

假设初始\(dp[i]=INF\).

重复以下做法：

目前所有没有出度的点都是\(dp\)值已经确定的值，它们不会构成环，对于后面点的贡献也是确定的，我们就可以进行拓扑排序，不断删去出度为0的点，这个贡献为\(dp_u=min(dp_u,max(r_i,dp_v-p_i))\)，注意了，这个\(v\)为我们要删去的点，遍历所有指向\(v\)的边\((u,v,r_i,p_i)\),按上诉公式计算贡献，并且删去此点还有所有边。

直到没有可以出度为0的点就说明没有影响现在\(dp\)的了，现在必处处成环，所以这样就有课以删除一个边，就是\(r_i\)最大的边，计算贡献，\(dp_u=min(r_i,dp[u])\)注意这里删去此边对之后是没有影响的，然后如果删去边后还是没有出度为0的点，证明所有点仍然被包含在全为环的图里，仍然可以删边，直到删到出现出度为0的点为止，因为这样我们就又可以进性拓扑排序了！