题意::
有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 |