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

    ACM-POJ EXP 157阅读 0评论

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


    大致题意

    某个企业想把一个热带天堂岛变成旅游胜地,岛上有N个旅游景点,任意2个旅游景点之间有路径连通(注意不一定是直接连通)。而为了给游客提供更方便的服务,该企业要求道路部门在某些道路增加一些设施。

    道路部门每次只会选择一条道路施工,在该条道路施工完毕前,其他道路依然可以通行。然而有道路部门正在施工的道路,在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景点。

    为了在施工期间所有旅游景点依然能够正常对游客开放,该企业决定搭建一些临时桥梁,使得不管道路部门选在哪条路进行施工,游客都能够到达所有旅游景点。给出当下允许通行的R条道路,问该企业至少再搭建几条临时桥梁,才能使得游客无视道路部门的存在到达所有旅游景点?

    解题思路

    做过 POJ2942 后,这题根本就是水题嘛= =

    首先建立模型

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

    模型很简单,正在施工的道路我们可以认为那条边被删除了。那么一个图G能够在删除任意一条边后,仍然是连通的,当且仅当图G至少为双连通的。

    PS:不要问我为什么不是3-连通、4-连通…人家题目问“至少添加几条边”好不…

    显然,当图G存在桥(割边)的时候,它必定不是双连通的。桥的两个端点必定分别属于图G的两个【边双连通分量】(注意不是点双连通分量),一旦删除了桥,这两个【边双连通分量】必定断开,图G就不连通了。但是如果在两个【边双连通分量】之间再添加一条边,桥就不再是桥了,这两个【边双连通分量】之间也就是双连通了。

    那么如果图G有多个【边双连通分量】呢?至少应该添加多少条边,才能使得任意两个【边双连通分量】之间都是双连通(也就是图G是双连通的)?


    这个问题就是本题的问题。要解决这个问题:

    1、 首先要找出图G的所有【边双连通分量】

    Tarjan算法用来寻找图G的所有【边双连通分量】是最简单有效的方法,因为Tarjan算法在DFS过程中会对图G所有的结点都生成一个Low值,而由于题目已表明任意两个结点之间不会出现重边,因此Low值相同的两个结点必定在同一个【边双连通分量】中! (如果是有重边的话,那么不同的low值是可能是属于同一个边双连通分量的,这个时候就要通过其他方法去求解边双连通分量。不过这不是本题要讨论的)

    2、 把每一个【边双连通分量】都看做一个点(即【缩点】)

    也有人称【缩点】为【块】,都是一样的。其实缩点不是真的缩点,只要利用Low值对图G的点分类处理,就已经缩点了。

    以样例1为例,样例1得到的图G为上左图,

    其中Low[4]=Low[9]=Low[10]

      Low[3]=Low[7]=Low[8]

      Low[2]=Low[5]=Low[6]

      Low[1]独自为政….

    把Low值相同的点划分为一类,每一类就是一个【边双连通分量】,也就是【缩点】了,不难发现,连接【缩点】之间的边,都是图G的桥,那么我们就得到了上右图以缩点为结点,已桥为树边所构造成的树。

    3、 问题再次被转化为“至少在缩点树上增加多少条树边,使得这棵树变为一个双连通图”

    首先知道一条等式

    若要使得任意一棵树,在增加若干条边后,变成一个双连通图,那么

    至少增加的边数 =( 这棵树总度数为1的结点数 + 1 )/ 2

    (证明就不证明了,自己画几棵树比划一下就知道了)

    那么我们只需求缩点树中总度数为1的结点数(即叶子数)有多少就可以了。换而言之,我们只需求出所有缩点的度数,然后判断度数为1的缩点有几个,问题就解决了。

    4、 求出所有缩点的度数的方法

    两两枚举图G的直接连通的点,只要这两个点不在同一个【缩点】中,那么它们各自所在的【缩点】的度数都+1。注意由于图G时无向图,这样做会使得所有【缩点】的度数都是真实度数的2倍,必须除2后再判断叶子。


    转载请注明:EXP 技术分享博客 » POJ3352 – Road Construction

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

    表情

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

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