搜索
POI0110跳舞蝇广西柳铁一中黄芸有一种奇妙的跳舞蝇。它们表演跳舞时，人们会先在桌上放n枚硬币。硬币从1至n编号。每枚硬币旁边都有一行题字：i→j，i是这枚硬币的编号，j是站在硬币i上的舞蝇下一步应该飞往的硬币编号。人们在每个硬币上放一只舞蝇，然后舞蝇就按照题字开始跳舞。可见，硬币的题字确定了跳舞蝇的表演。然而，对硬币不同的设置也可能导致相同的表演，只要适当调整硬币。题目1321→22→33→1表演不相同例一1321321→22→33→11→22→33→31→2表演相同34213421例二2→34→43→24→33→22→31→1请编写一个程序●对给出的两组硬币设置，验证是否能适当调整硬币,使跳舞蝇给出相同的表演。能够,输出“T”；不能，输出“N”。任务Pch.in23231233423241323Pch.outNT任务数d硬币数n硬币数n表演不相同表演相同输入输出格式1=d=1001=n=2000数据规模I.N枚硬币；II.硬币的题字：i→j；III.硬币的设置决定表演；IV.表演是否相同。判断两个图是否同构。题意的抽象：同构1)定义：图G1和G2,它们的顶点集和边集之间都分别建立了一一对应的关系，并且G1的两顶点间的边对应G2对应顶点间的边，则称图G1和G2互为同构。2)方法：n枚举顶点集的对应关系；判断当前关系下的各条边是否一一对应。n时间复杂度为O（n！）。对本题n＜＝2000，该方法不可行。同构●“同”:相同,本质相同判断数字矩阵的本质是否相同定义大小关系；求出本质相同的最小表示；比较最小表示。●“构”：图的构成研究本题所指的图的特殊性，期望能应用最小表示的思想。0101101011000011001101011010110000110011最小表示图的特殊性a.点的出度均为1。b.点的类别:a).圈上的点;b).圈外的点,构成树形,与圈相连.c.圈与圈之间无边相连.证明：若两圈相连,则必有一点出度为2(如图)，与题意矛盾。点i或者点id.这种图由若干个之间无边相连的子图组成，每个子图都是把若干棵树的根结点串成一个圈而构成的。算法的框架1.判断树的同构；2.判断子图的同构；3.判断整个图的同构。根据图的构成,从小做起,从简单到复杂：图子图树一．判断树的同构1．定义树的大小：a.若树Ａ根结点的度数〉树Ｂ根结点的度数，则树Ａ〉树Ｂ；b.若树Ａ根结点的度数〈树Ｂ根结点的度数，则树Ａ〈树Ｂ;c.若树Ａ根结点的度数＝树Ｂ根结点的度数,则依次讨论Ａ与Ｂ的子树,拥有较大子树的树较大若当前子树相等，则讨论A与B的下一棵子树。(b)(a)(a)(b)3．判断树A与树B是否同构：分别求出树A与树B的最小表示A’和B’若A’＝B’，则树A与树B互为同构;反之，没有同构关系。2．本质相同的树具有共同的最小表示(a)(b)二．判断子图的同构求出子图的最小表示；若两子图最小表示相等，则它们互为同构．把圈断开,把子图化为一棵树;把所有的树均化为其最小表示;最小三．判断图的同构各子图的最小表示图的最小表示●对图的处理:1.把图分为若干子图;2.把子图分为若干棵树.●主过程1.求树的最小表示求子树的最小表示,对子树排序.2.求子图的最小表示断圈,化成树,求最小.3.求图的最小表示给子图排序,合并成一棵树.●比较两图的最小表示,判断是否同构.贯穿整个算法的线索最小表示归纳算法的性能分析空间复杂度:O(n)时间复杂度:约为O(n^3)。但受到子图个数，各子图规模的影响，远远达不到O(n^3)。总结●触类旁通●善于分化问题●把握问题的特殊性谢谢!