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

    ACM-POJ EXP 151阅读 0评论

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


    大致题意

    为了保护放牧环境,避免牲畜过度啃咬同一个地方的草皮,牧场主决定利用不断迁移牲畜进行喂养的方法去保护牧草。然而牲畜在迁移过程中也会啃食路上的牧草,所以如果每次迁移都用同一条道路,那么该条道路同样会被啃咬过度而遭受破坏。

    现在牧场主拥有F个农场,已知这些农场至少有一条路径连接起来(不一定是直接相连),但从某些农场去另外一些农场,至少有一条路可通行。为了保护道路上的牧草,农场主希望再建造若干条道路,使得每次迁移牲畜时,至少有2种迁移途径,避免重复走上次迁移的道路。已知当前有的R条道路,问农场主至少要新建造几条道路,才能满足要求?

    解题思路

    “使得每次迁移牲畜时,至少有2种迁移途径,避免重复走上次迁移的道路。”就是说当吧F个农场看作点、路看作边构造一个无向图G时,图G不存在桥。

    那么可以建立模型

    给定一个连通的无向图G,至少要添加几条边,才能使其变为双连通图。

    这题是和 POJ3352 一模一样的题,只不过表述方式不同而已。

    详细解题过程请参考我 POJ3352 的解题报告,有详细叙述。

    看完 POJ3352 的解题报告,再回来看看本题要注意的一些地方:

    本题和 POJ3352 最大的区别就是, POJ3352 保证了没有重边,而本题有重边

    POJ3352 的解题报告已经说过,当两点之间出现重边时,就不可以利用Low值去划分【边双连通分量】了,因为此时不同Low值的两点可能属于同一个【边双连通分量】!


    那么如何解决重边的问题

    1、 构造图G时把重边也考虑进来,然后在划分边双连通分量时先把桥删去,再划分,其中桥的一端的割点归入当前正在划分的边双连通分量。这个处理比较麻烦;

    2、 在输入图G的边时,若出现重边,则不把重边放入图G,然后在划分边双连通分量时依然用Low划分。

    两者相权,当然是第2种方法更好处理了。

    其实用邻接矩阵去存储图G的同学,是无需考虑重边的问题的

    但是用邻接链表去存储图G的同学就不得不考虑了,因为基本上都是用头插入法在链表中插入边的,所以无法检测重边。而改用尾插入法,则可以在指针从链头移到链尾的同时,顺便加一个判断,出现重边则不再插入,否则插入到尾部。

    测试数据

    本文第二页附带测试数据


    转载请注明:EXP 技术分享博客 » POJ3177 – Redundant Paths

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

    表情

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

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