《Thimbles》解题报告

《Thimbles》解题报告

问题简述

有一个简单的游戏：桌上放着n个圈，编号从1到n，在圈1中有一个小球。现有一系列指令，每条指令都是一对数(u, v) (1,,)

≤≤≠，执行一条指令

u v n u v

(u,v) 则：

1）如果小球在圈u，则将其移动到圈v；

2）如果小球在圈v，则将其移动到圈u；

3）如果小球不在圈u，v，则不进行任何操作。

指令可以按照任意的顺序排列，但都必须执行。请求出将指令任意排列并全部执行完以后，小球能停留在哪些圈中。

分析

构造一个无向图G，将圈i对应成图G中的顶点i，而指令(u，v)对应成图G 中一条无向边(u，v)。那么可以将执行指令进行新的定义，如果当前点为x，执行指令(u, v)，如果x=u或者x=v则进行一次移动后删去边(u,v)，否则即是直接删去边(u, v)。

显然和1不在同一个连通分量内的点是无法到达的，更不可能停留。这样就只需考虑1所在的连通分量内的点，下面提到的所有的点即是和1同在一个连通分量内的点。

1）如果过点1有一个长度不小于3的环，设为C1-C2-C3…-C m-C1,其中C1=1，可分以下几种情况讨论：

a)C3..C m中的某个点C k：确定小球移动路径为C1-C2...C k。在C1删去所

有和C1无关的非路径边，走到C2并且删去所有和C2无关的非路径

边，沿着路径走到C k并且删去所有（C1，C2）边。YES!

b)C2：方法和a)类似，确定路径为C1-C m-C m-1...C2。在C1删去所有和

C1无关的非路径边，走到C m并且删去所有和C m无关的非路径边，

沿着路径走到C2并且删去所有（C1，C m）边。YES!

c)C1：确定路径为C1-C2…-C m-1-C m-C1。在C1删去所有和C1无关的非

路径边，走到C2并且删去和C1相连的，不是（C1，C2）的非路径边，

走到C3删去（C1，C2），沿着路径走回C1。YES!

d)其他的点T：确定一条路径P1-P2-P3…P k,其中P1=C1，P2=C2，P k=T。

在C1删去所有和C1无关的非路径边，走到C2并且删去和C1相连的，

不是（C1，C2）的非路径边，沿着路径走到目标点T删去所有

（C1，C2）边。YES!

按照上述方法推出每个点都是可以最后停留的。

上面讨论了当存在长度不小于3的环时，对于图中的各个点，是如何处理。虽然处理方法不同，但大致都是按照这样一种思路：首先确定一条从1到目标点长度不小于3的路径，然后在沿着路径走的过程中删去其他边。而删边也往往先在点1删掉和1无关的边，然后走到第二个点删掉和该点无关的边，再走到最后点删去点1和路径中第二个点之间的所有边。

照着上面分析出来的思路，我们可以继续分类。这里对第I类的讨论都是其不满足第1~I-1类的情况下展开的。

2）如果有不少于2个点与1有多于1条边：

这种情况和第一种情况很类似，也就是至少有两个点和1构成了环，所

以按照类似1）的分类及处理可以得到所有点也都是可以到达的。

3）恰有一个点K与1有多于1条边：

此时只有1个点与1构成环，那么还需要继续分类

I）如果过点K还有1个不包括1的环，显然又类似于1）、2）的情况，可以停留在任意点。

否则，当目标点为1和K的时候就无法找到另一个点来暂停以删去边（1，K），这样需要按（1，K）边的条数来分类。

II）如果（1，K）有奇数条，则点1无法到达。

III）如果（1，K）有偶数条，则点K无法到达。

4）没有点与1有多于1条边；

此时1不在任何一个环中。

I）如果有边与1相连，则显然走出1就无法再返回，所以点1无法停留。而其他点T则可以找到一条1到T的路径，在点1删去和

1无关的非路径边，再在点T删去其他所有边。

II）没有边与1相连，显然只能到停留在点1。

所有分类完成，只需要对图G进行遍历，找圈以及询问边数，所以其时空复杂度均为O（m）或者O(n2)。

再来回顾一下该题的解题过程。本题显然是一道分类讨论的题目，因为其情况较繁杂，所以首先通过对一种较简单情况（有长度不小于3的环）的分析，总结出一套处理思路，然后按着该思路来分类，每一类处理方法也大致相同。这样就做到了无遗漏，无重复的处理了所有情况。

【题目来源】

ACM ICPC 2004-2005, NEERC, Southern Subregional Contest

Saratov State University problemset archive 270