黄芸 跳舞蝇.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
最小表示