国家集训队2002论文集黄芸.ppt

POI0110 跳舞蝇 广西柳铁一中 黄芸 * * 有一种奇妙的跳舞蝇。它们表演跳舞时，人们会先在桌上放n枚硬币。硬币从1至n编号。每枚硬币旁边都有一行题字：i→j，i是这枚硬币的编号，j是站在硬币i上的舞蝇下一步应该飞往的硬币编号。人们在每个硬币上放一只舞蝇，然后舞蝇就按照题字开始跳舞。 可见，硬币的题字确定了跳舞蝇的表演。然而，对硬币不同的设置也可能导致相同的表演，只要适当调整硬币。 题目 1 3 2 1→2 2→3 3→1 表演不相同 例一 1 3 2 1 3 2 1→2 2→3 3→1 1→2 2→3 3→3 1→2 表演相同 3 4 2 1 3 4 2 1 例二 2→3 4→4 3→2 4→3 3→2 2→3 1→1 请编写一个程序 ● 对给出的两组硬币设置，验证是否能适当调整硬币, 使跳舞蝇给出相同的表演。 能够, 输出“T”； 不能，输出“N”。 任务 Pch . in 2 3 2 3 1 2 3 3 4 2 3 2 4 1 3 2 3 Pch . out N T 任务数d 硬币数n 硬币数n 表演不相同 表演相同 输入输出格式 1=d=100 1=n=2000 数据规模 N枚硬币； 硬币的题字：i→j； 硬币的设置决定表演； 表演是否相同。 判断两个图是否同构。 题意的抽象： 同构 定义： 图G1和G2, 它们的顶点集和边集之间都分别建立了一一对应的关系，并且G1的两顶点间的边对应G2对应顶点间的边，则称图G1和G2互为同构。 方法：n??枚举顶点集的对应关系；判断当前关系下的各条边是否一一对应。 　　　　　n?? 时间复杂度为O（n！）。　　 对本题n＜＝2000，该方法不可行。 同构 ● “同”: 相同,本质相同 　 判断数字矩阵的本质是否相同 　 ? 定义大小关系； ? 求出本质相同的最小表示； 　 ? 比较最小表示。 ● “构”：图的构成 　 研究本题所指的图的特殊性，期望能应用最小表示的思想。 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0011 0101 1010 1100 0 0 1 1 0011 最小表示 图的特殊性 a. 点的出度均为1。 b. 点的类别: a).圈上的点; b).圈外的点, 构成树形,与圈相连. c. 圈与圈之间无边相连. 证明：若两圈相连, 则必有一点出度为2(如图)，与题意矛盾。 点i 或者 点i d. 这种图由若干个之间无边相连的子图组成，每个子图都是把若干棵树的根结点串成一个圈而构成的。 算法的框架 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. 求图的最小表示 给子图排序, 合并成一棵树. ● 比较两图的最小表示, 判断是否同构. 贯穿整个算法的线索 最小表示 归纳