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

    ACM-POJ EXP 203阅读 0评论

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


    提示

    难得的中文题。。虽然语言相通但是不好解决。。。都说便宜没好货,这是真的= =

    最短路问题dijkstra算法的运用。。。很多同学对dijkstra有一种与生俱来的恐惧,首当其冲就是它的名字。。说实在我现在也不知道怎么念它O(∩_∩)O哈哈~

    其实dijkstra很简单的,最难也就它的名字,不懂得同学去翻书,这里我不解释dijkstra,

    我只说一个我认为能够很好理解dijkstra精髓的关键点:

    新源点合并到旧源点时,新源点到旧源点的边权的移交(也可理解为松弛)

    弄清了这个,dijkstra就不难了,我觉得dijkstra和Prim有异曲同工之妙


    大致题意

    每个物品看成一个节点,酋长的允诺也看作一个物品, 如果一个物品加上金币可以交换另一个物品,
    则这两个节点之间有边,权值为金币数,求第一个节点到所有节点的最短路。
    因为有等级限制,所以枚举每个点作为最低等级,选取符合所有符合等级限制的点

    解题思路

    最短路问题,不过因为存在着等级的差异所以需要枚举一下。本题的思路就是对冒险者的等级进行枚举,也就是说冒险者只能和在他等级以上的人进行交易。这样枚举的好处是能够把所有的情况都考虑进去。有一点需要注意:酋长的等级不一定是最高的

    构图时要注意的是,酉长的承诺不是 最初的源点,它是一个目标点,也就是说点到点的指向方向是由 无替代品的点 逐渐指向到 酉长的承诺1点,题意说明的是一个回溯的过程,因此可以定义一个最初的源点0点,它到其他各点的权值就是每个物品的原价,而点A到点B的权值 就是 物品B在有第A号替代品情况下的优惠价

    转载请注明:EXP 技术分享博客 » POJ1062 – Expensive dowry

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

    表情

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

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