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

    ACM-POJ EXP 224阅读 0评论

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


    大致题意

    有n座城市和m(1<=n,m<=10)条路。现在要从城市1到城市n。有些路是要收费的,从a城市到b城市,如果之前到过c城市,那么只要付P的钱,如果没有去过就付R的钱。求的是最少要花多少钱。

    注意:路径是有向的

    解题思路

    DFS。这题当有了思路后,做起来是没有难度的,但是思维推算能力要求很高。

    这题难点在于“城市与城市之间可能存在多条路径”

    1、 输入数据时可能会出现多条 从城市a到城市b的路径信息,但是费用有所差别;

    2、 对于 从城市a到城市b 的同一条路径,允许重复走。


    有人会问,重复走同一条路径有什么意义?单纯增加费用而已,为什么不能标记所有路径,每条路只允许走一次,这样费用不是更少么?

    我开始也是陷入了这种思维,但是这种想法其实“对一半,错一半”。

    先来看一组数据:

    6 5

    1 2 1 10 10

    2 3 4 10 100

    2 4 2 15 15

    4 1 1 12 12

    3 6 6 10 10

    如果每条路只允许走一次,那么方案只有1个:

    1->2->3->6 共135元

    但这组数据的正确答案是67元。为什么?正确的方案如下:

    1->2->4->1->2->3->6 共67元

    显然1->2重复走了一次,目的是为了先到达城市4,从而使得2->3这段路的费用从100缩减到10元。

    看到这里很多同学好像就恍然大悟,但是问题马上又来了。如果同一条路允许重复走,那么就不能标记了,但一旦不标记,失去了搜索的限制条件,DFS就无法结束,不是陷入死循环了?

    我刚才说这种思路“对一半,错一半”,“对”是对在“重复走会增加费用”,“错”是错在“重复走的对象不是某一条路,而是某一个环路”。在同一个环路重复走才会真正增加费用。但是标记环路是很麻烦的,那么能不能根据某一条路或某一个城市重复走过的次数来判断当前所走的方案已经出现了环路? 答案是可以的。

    上述的例子已经验证过了,同一条路可以重复走,但是不能无限重复走,重复的次数是有限的。那么应该重复多少次才合理?这与m值有关。题目的m值范围为<=10,那么当人一个城市被到达的次数若 >3次(不包括3),所走的方案必然出现了环路(网上的同学称之为“闸数”)。

    因此只需把bool vist[] 修改为 int vist[] 进行标记,本题就能解决了。


    PS:最近刚刚接触了C++的面向对象,所以程序用class写了一次,用C风格写了一次。

    测试数据

    本文第三页附带测试数据

    注意边界数据:当输入n==1时,输出花费恒为0


    风格一:C++面向对象

    转载请注明:EXP 技术分享博客 » POJ3411 – Paid Roads

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

    表情

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

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