算法合集之《POI0110 跳舞蝇》-课件【PPT讲稿】.ppt

POI0110 跳舞蝇广西柳铁一中黄芸有一种奇妙的跳舞蝇。它们表演跳舞时,人们会先在桌上放 n 枚硬币。硬币从 1至n 编号。每枚硬币旁边都有一行题字: i→j,i 是这枚硬币的编号, j 是站在硬币 i 上的舞蝇下一步应该飞往的硬币编号。人们在每个硬币上放一只舞蝇,然后舞蝇就按照题字开始跳舞。可见,硬币的题字确定了跳舞蝇的表演。然而,对硬币不同的设置也可能导致相同的表演,只要适当调整硬币。题目 132 1→22→33→1 表演不相同例一 13 2 132 1→22→33→1 1→22→33→3 1→2表演相同 34 2134 21 例二 2→34→43→24→33→2 2→31→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 数据规模 ; : i→j; III. 硬币的设置决定表演; IV. 表演是否相同。判断两个图是否同构。题意的抽象: 同构 1)定义: 图 G1 和 G2, 它们的顶点集和边集之间都分别建立了一一对应的关系,并且 G1 的两顶点间的边对应 G2 对应顶点间的边,则称图 G1 和 G2 互为同构。 2)方法: ?枚举顶点集的对应关系;判断当前关系下的各条边是否一一对应。?时间复杂度为 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 最小表示