最优贸易

最优贸易
这题主要是求一条路径上顺序的两个点的差的最大值,题目给出的边可能是单向边,也可能是双向边,对于求单一路径上最大值和最小值还是很好求的嘛,BFS一下我们就很好的求出这个答案了=v=。
但是怎么求两个顺序的点呢?
那么我们分解一下问题。
我们枚举每一个点,我们可以求出源点到这个点的最小价值路径,那么我们只需要看看有没有一条最大路径连到终点就好。
我们还可以重新连一次反向图,倒过来建边,然后从终点跑一次维护到每一个点的最大值,最后枚举每个点,最大最小值减一减就好。

发表评论

电子邮件地址不会被公开。 必填项已用*标注