集训队作业rooksuva10615解题报告

1、IOI2004国家集训队作业：解题报告 安徽 周源Rooks（UVA 10615）解题报告安徽 周源摘要算法构造时间复杂度O(N3)空间复杂度O(N2)题意简述给定一个N * N的棋盘，上面放有一些棋子（都是車）。你需要用最少的颜色去给这些車染色，满足任意同一行或者同一列没有两个或两个以上的車是相同颜色的。分析如果把这个棋盘看作一个二分图，将每一行“抽”出来，看作是二分图一边的N个结点（X集合）；同样将每一列也“抽”出来，看作二分图另外一边的N个结点（Y集合）。如果第x行y列的方格中有棋子，对应在二分图上就可以看作是在左边X集合中的结点x和右边Y集合中的结点y之间连一条边。而题目中的问题就是求

2、这个二分图的最小边染色数。不妨来看这样一个定理：定理1在一个二分图中，假设图中两部分的结点个数都为N，且度数最大的结点的度是dmax，则一定有一个匹配，能覆盖所有度为dmax的结点（即所有度最大的点）。并且至少有一个O(N3)的算法能够找到这个匹配。定理1的证明首先使用归纳法进行证明：对图中边的数目进行归纳。当边数为0的时候，显然空匹配就是满足条件的。现在试图在某一个已经确定有满足条件的匹配的图上加一条边，并证明通过调整仍然可以找到满足条件的匹配。假设加入的这条边是(u, v)，其中uX且vY，且(u, v)并不与图中已有的边重复。接着，分以下几种情况讨论： d(v)表示v的度，同理可知d(u

3、)表示结点u的度数。在未加入(u, v)的时候，d(u)dmax-1且d(v)dmax-1：那么在加入边(u, v)以后，仍然有d(u) , d(v) dmax或是d(v) dmax。也就是说d(u)或是d(v)会成为新的dmax：则加入(u, v)以后，最大度发生了变化，新的度最大的点仅有一个（或两个）：反正都被(u, v)这条边覆盖了。因此在这种情况下，清空匹配，保留(u, v)边作为新的匹配即可。不满足上面两种情况，且在未加入(u, v)的时候，d(u) = dmax 1或d(v) = dmax 1：那么加入边(u, v)以后，u和v中至少有一个会成为度最大的点。此时情况较为复杂，仍分三

4、种情况：如果u和v都不在原先的匹配中，那么将(u, v)边加入匹配就可以了。如果将变为度最大的点都在原先的匹配中，那么不需要对匹配做任何修改。如果某一个将变为度最大的点不在原先的匹配中，而另外一个点却在原先的匹配中：由对称性，我们可以设v在原先的匹配中而u不在，可偏偏在加入(u, v)之前就有d(u) = dmax 1。这个时候，我们的目标就是通过一些调整，让u进入匹配，而不影响其它度最大的点。我们先将(u, v)边加入图中，同时修改d数足，并从u结点出发寻找一条未匹配边与匹配边交替出现的路径：交替路。由于u 不在原先的匹配中，因此从u出发的边都是未匹配边，而从u出发到达的每一个点y1，一般来

5、说如果这个点y1在匹配上，那么沿着他的匹配边逆向找回到X这边来，假设找到了x1点，并再次从x1出发寻找一条未匹配的边到达y2这样一直继续下去：直到遇到以下两种情况的时候停止查找：在找到Y一部分的时候，某个点yi不在匹配上，那么此时我们找到的交替路则是： “”表示匹配边，“-”表示为匹配边u-y1x1-y2x2-xi-1-yi这个时候将这个交替路上的匹配边和未匹配边交换，得到：uy1-x1y2-x2-xi-1yi可以看出，此时除了u加入匹配，其他点都仍在匹配中，因此这个调整是合法的。在找到X一部分的时候，某个点xi的度d(xi)不等于dmax（也就是小于）。此时我们找到的交替路是：u-y1x1-

6、y2x2-xi-1-yixi同样将这个交替路上的匹配边和为匹配边互换，得到：uy1-x1y2-x2-xi-1yi-xi可以看出，此时u进入了匹配，而xi退出了匹配。u进入匹配是众望所归，而xi并不是度最大的点，其退出匹配也是合情合理。所以在这种情况下，我们的调整也是正确的。那么是不是所有情况下，寻找交替路都会如此顺利的碰到这两种情况而停下来，是不是有可能永远无法遇到这两种情况而导致死循环呢？假设永远都无法碰到这两种情况，也就是从u开始搜索交替路，遇到所有Y部分的点构成点集，其中的所有的点都在X部分有匹配点，因此搜索算法又扩展到了X部分的一些点，构成点集，而中所有的点的度数都是dmax，且到达“

7、死循环”的时候，中所有点连出的边都在中：这些都是构成“死循环”必备的条件。显然中除了u以外所有的点都在中有一一对应的匹配，中所有的点在中也有匹配，因此可以得到| = | + 1接着中所有点的度数之和d() = | * dmax，而这些“度”代表的边都连向了，所以有：d() d() = | * dmax = (| + 1) * dmax所以集合中所有点的度数的“平均值”至少是“平均值”都大于dmax，那么至少有一个点的度数要比dmax要大，而这显然是不可能的。因此“会出现死循环”的担心是多余的。至此，可能会遇到的情况都在我们的讨论之中了。因此定理1的正确性是毋庸置疑的了。而这个证明本身就是构造型

8、的，这个算法至少要加入O(N2)条边，而每加入一条边，最坏情况下需要查找一条交替路，这一步最坏情况下是O(N)的，因此整个算法的时间复杂度是O(N3)。定理1证明完毕。定理2二分图的边染色数就是这个二分图所有结点的最大度数。并且至少有一个O(N4)的算法找到这个染色方案。定理2的证明假设最大度为dmax，显然至少需要dmax种颜色才能满足度最大点的染色要求。下面只需要构造一种方法得到只需要dmax种颜色的染色方案即可。每次对当前的二分图执行一次定理1中的算法，可以得到一个匹配，为这个匹配上的边单独安排一种颜色，并删除匹配上的边。由于每次匹配都可以让度数最大的点都被覆盖，因此删除匹配后dmax一定会减一，这样一共会减dmax次，每次安排一种颜色，所以一共需要dmax种颜色。根据这个方法，一共需要执行dmax = O(N)次定理1中的算法，每次执行需要O(N3)的时间，因