{"trustable":false,"sections":[{"title":"题意","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 有多种汇币,汇币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 - 0.39) * 29.75 \u003d 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加\n\n货币的交换是可以重复多次的,所以我们需要找出是否存在正权回路,且最后得到的s金额是增加的\n\n怎么找正权回路呢?(正权回路:在这一回路上,顶点的权值能不断增加即能一直进行松弛)\n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 2 1 20.0\n1 2 1.00 1.00 1.00 1.00\n2 3 1.10 1.00 1.10 1.00\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003eYES\u003c/pre\u003e"}},{"title":"题解","value":{"format":"HTML","content":"\n一种货币就是一个点\n\n一个“兑换点”就是图上两种货币之间的一个兑换方式,是双边,但A到B的汇率和手续费可能与B到A的汇率和手续费不同。\n\n\n唯一值得注意的是权值,当拥有货币A的数量为V时,A到A的权值为K,即没有兑换\n\n而A到B的权值为(V-Cab)*Rab\n\n本题是“求最大路径”,之所以被归类为“求最小路径”是因为本题题恰恰与bellman-Ford算法的松弛条件相反,求的是能无限松弛的最大正权路径,但是依然能够利用bellman-Ford的思想去解题。\n\n因此初始化dis(S)\u003dV 而源点到其他点的距离(权值)初始化为无穷小(0),当s到其他某点的距离能不断变大时,说明存在最大路径;如果可以一直变大,说明存在正环。判断是否存在环路,用Bellman-Ford和spfa都可以。\n"}}]}