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

    ACM-POJ EXP 166阅读 0评论

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


    大致题意

    给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。

    解题思路

    可以用图论欧拉路的知识来解这道题,首先可以把木棒两端看成节点,把木棒看成边,这样相同的颜色就是同一个节点

    问题便转化为

    给定一个图,是否存在“一笔画”经过涂中每一点,以及经过每一边一次。

    这样就是求图中是否存在欧拉路Euler-Path

    回顾经典的“七桥问题”,相信很多同学马上就明白了什么是 欧拉路 了,这里不多作解释。

    由图论知识可以知道,无向图存在欧拉路的充要条件为

    ① 图是连通的;

    ② 所有节点的度为偶数,或者有且只有两个度为奇数的节点。

    其中①图的连通性用程序判断比较麻烦,先放一下。

    这里先说说②关于度数的判断方法:

    节点的度用颜色出现次数来统计,如样例中,蓝色blue出现三次(不管是出度还是入度),那么blue结点的度就为3,同样地,我们也可以通过输入得到其他全部结点的度,于是,我们有:

    Blue=3

    Red=2

    Violet=1

    Cyan=2

    Magenta=2

    用一个一维数组就能记录了,然后分别 模2,就能判断颜色结点的奇偶性

    只要奇度数的结点数的个数 = 1 或 >=3 ,即使①图连通,欧拉路也必不存在

    但是若 奇度数的结点数的个数 为0或 ==2,那么我们继续进行①图的连通性证明:

    证明①图的连通性,使用并查集MergeSet是非常高效的方法

    基本方法:

    初始化所输入的n个结点为n棵树,那么就有一个n棵树的森林,此时每棵树的有唯一的结点(根),该结点的祖先就是它本身。再通过不断地输入边,得到某两个结点(集合)之间的关系,进而合并这两个结点(集合),那么这两个集合就构成一个新的集合,集合内的所有结点都有一个共同的新祖先,就是这个集合(树)的根。

    最后只要枚举任意一个结点,他们都具有相同的祖先,那么就能证明图时连通的了。

    但是单纯使用并查集是会超时的,因为这样会导致每次寻找某个结点的祖先时,平均都会花费O(n/2)时间,最坏情况,当n==50W时,O(n/2)大概为25ms,那么要确定50W个结点是否有共同祖先时,总费时为50W*25ms ,铁定超,不算了= =

    因此必须使用并查集时必须压缩路径,前几次搜索某个结点k的祖先时,在不断通过父亲结点寻找祖先结点时,顺便把从k到最终祖先结点S中经过的所有结点的祖先都指向S,那么以后的搜索就能把时间降低到O(1)

    由于并查集必须利用 数组的下标 与 存储的对象,使用int是比较方便的处理方法,但是题目的“颜色结点”是string,不方便用来使用并查集,即使用map也不行,虽然STL的map是基于hash的基础上,但并不高效,在本题中使用会超时。

    为此可以使用Trie字典树,得到每个颜色单词对应的int编号id ,可以说利用Trie把string一一映射到int,是本题后续处理的关键所在。关于动态创建字典树的方法去百度,这里不多说,下面只用用一个图简单说明一下用Trie字典树标识第一个颜色单词blue:

    这个题目涉及了多个基本数据结构和算法,综合性很强,非常有代表性,能够A到这题确实是受益良多。

    知识考查点

    1、字典树

    2、欧拉路径:其中又考察了判断是否为连通图;

    3、并查集 及其优化方法(路径压缩)。

    输出

    POSSIBLE: 奇度数结点个数==0 或 ==2 且 图连通

    IMPOSSIBLE:奇度数结点个数==1 或 >=3 或 图不连通

    PS: 注意创建TrieTree链表时,C++不存在NULL,要用 0 替代 NULL

    转载请注明:EXP 技术分享博客 » POJ2513 – Colored Sticks

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

    表情

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

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