/* POJ 1860 有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币 交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到 (100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终 得到的s币金额数能否增加 货币的交换是可以重复多次的，所以我们需要找出是否存在 正权回路，且最后得到的s金额是增加的 怎么找正权回路呢？（正权回路：在这一回路上，顶点的权值能不断增加即能一直进行松弛） 关键在于反向利用Bellman-Ford算法 单源最短路径算法，因为题目可能存在负边，所以用Bellman Ford算法， 原始Bellman Ford可以用来求负环，这题需要改进一下用来求正环 一种货币就是图上的一个点 一个“兑换点”就是图上两种货币之间的一个兑换环，相当于“兑换方式”M的个数，是双边 唯一值得注意的是权值，当拥有货币A的数量为V时，A到A的权值为K，即没有兑换 而A到B的权值为(V-Cab)*Rab 本题是“求最大路径”，之所以被归类为“求最小路径”是因为本题题恰恰 与bellman-Ford算法的松弛条件相反，求的是能无限松弛的最大正权路径， 但是依然能够利用bellman-Ford的思想去解题。 因此初始化d(S)=V 而源点到其他店的距离（权值）初始化为无穷小（0）， 当s到其他某点的距离能不断变大时，说明存在最大路径 POJ 1860 有多种汇币，汇币之间可以交换，这需要手续费，当你用
阅读背景：
POJ 1860 Currency Exchange（BellmanFord算法的变形，求正环）
来源：互联网
分享到：
