当前位置: 代码迷 >> 综合 >> POJ1860 Currency Exchange(最短路径)
  详细解决方案

POJ1860 Currency Exchange(最短路径)

热度:93   发布时间:2024-01-16 13:46:04.0

题意::

有n种货币,m种兑换方式,每次兑换是这样计算的:如果一开始有V单位b货币,Rab是从a换到b的汇率,Cab是交换需要的手续费,最后能换到(V-Cab)*Rab单位b货币。一开始的货币种类是s,要求最后换回s,问能否进行一系列兑换,使最后换回s时钱增加。

要点:

如果能够经过一个回路返回起点使钱增加,那么可以经过无数次回路,使钱无限增多。所以就转化为bellman算法求是否有负权回路问题,只不过这题稍微变形了一下,恰恰与bellman算法的松弛条件相反,求的是能无限松弛的最大正权路径,因此初始化d(S)=V 而源点到其他店的距离(权值)初始化为无穷小(0),当s到其他某点的距离能不断变大时,说明存在最大路径。这题我WA了很多次,明明思路对的,最后发现我代码里用了两个v,一个表示初始金钱,一个表示边的终点。下次变量多的题尽量用长的变量名称。


15377480 Seasonal
  相关解决方案