题意不多赘述。
注：全文所用的“点 \(u\) 的出度”均指的是点 \(u\) 在原图上的出度。
首先我们考虑 \(r_{i} = 0\) 的情况怎么写，这时我们会发现要么答案是 \(0\) 要么无解。当当前点 \(u\) 无论怎么走都走不到一个环上，即无论怎么走最终都会走到一个出度为 \(0\) 的点上的话，那么显然这个点是无解的。否则一定有解，因为可以先走到一个环上，然后在环上无限走。
然后考虑正解。可以发现一些性质：
-
性质一：如果一个点的出度为 \(0\) 的话，那么这个点一定无解。
-
性质二：对于一条边 \(u \to v\)，如果点 \(v\) 的出度为 \(0\) 的话，那么删除这条边对答案没有影响。
-
性质三：如果当前边 \(u \to v\) 的 \(r\) 值是它所在环中 \(r\) 值最大的，那么 \(u\) 点的答案一定小于等于当前 \(r\)。
-
性质四：如果当前边 \(u \to v\) 的 \(r\) 值是剩下所有边中 \(r\) 值最大的，那么 \(u\) 点的答案一定小于等于当前 \(r\)。
那么我们可以先考虑一个类似于拓扑序上 dp 的东西，设 \(dp_{v}\) 表示 \(v\) 点的答案，对于一条边 \(u \to v\)，则有：
\(dp_{u}=\min(dp_{u},\max(r_{u \to v},dp_{v}-p_{u \to v}))\)。
因为 dp 方程的转移 \(u\) 和 \(v\) 是反过来的，所以建反图跑 dp。
但是给定的图不是 DAG，不好直接在拓扑序上 dp，于是考虑加上一些贪心。
先将所有边按照 \(r\) 的值从大到小排序，枚举每一条边。对于每一条边先进行一次拓扑排序，在队列里的点表示当前点的 dp 值已经确定了的点，遍历它的出边 \(u \to v\)，用它来更新其它点即可。注意拓扑排序中遍历过的边可以直接删除了，因为 dp 值已经转移了，所以这条边已经没有任何价值了。同时 \(v\) 点的出度减一，如果 \(v\) 点的出度变为 \(0\) 了，则入队。
进行完拓扑排序过后，如果当前枚举到的边还没有被删除的话，那么可以直接用性质四来更新答案，并将这条边删掉。因为如果一条边会被删掉必须满足它只能走到一些出度为 \(0\) 的点上，而这条边还没有被删除所以它一定在一个环中，又因为 \(r\) 值是从大到小枚举的，所以可以这样更新。
排序时间复杂度 \(O(m \log m)\)，dp 时间复杂度 \(O(m)\)，总时间复杂度 \(O(m \log m)\)。
标签：Merchant,当前,P7831,拓扑,答案,Travelling,排序,出度,dp From： https://www.cnblogs.com/Creeperl/p/17913414.html