• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1860 – Currency Exchange

    ACM-POJ EXP 280阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    提示

    关键在于反向利用Bellman-Ford算法

    题目大意

    有多种汇币,汇币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 – 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加

    货币的交换是可以重复多次的,所以我们需要找出是否存在正权回路,且最后得到的s金额是增加的

    怎么找正权回路呢?(正权回路:在这一回路上,顶点的权值能不断增加即能一直进行松弛)

    题目分析

    一种货币就是图上的一个点

    一个“兑换点”就是图上两种货币之间的一个兑换环,相当于“兑换方式”M的个数,是双边

    唯一值得注意的是权值,当拥有货币A的数量为V时,A到A的权值为K,即没有兑换

    而A到B的权值为(V-Cab)*Rab

    本题是“求最大路径”,之所以被归类为“求最小路径”是因为本题题恰恰与bellman-Ford算法的松弛条件相反,求的是能无限松弛的最大正权路径,但是依然能够利用bellman-Ford的思想去解题

    因此初始化d(S)=V 而源点到其他店的距离(权值)初始化为无穷小(0),当s到其他某点的距离能不断变大时,说明存在最大路径

    转载请注明:EXP 技术分享博客 » POJ1860 – Currency Exchange

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址