flare

Size: px

Start display at page:

Download "flare"

艳水田
5 years ago
Views:

1 flare 解题报告福州一中卓亮 April 30, 2012 Contents 1 题意简述 3 2 命题思路 3 3 考查点 5 4 问题分析 6 5 数据生成方法 12 6 选手得分统计 12 7 后记 12 Appendices 16 A flare 完整题面 16 B Glossary of graph theory 17 C Usage of the program 17 圱

2 List of Figures 圱一个 E 1 圽圂在 E 0 2 圩的情形圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圴圲 G 2 中的点对应至 G 0 圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圴圳 G 2 中的边对应至 G 0 圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圵圴效果相同的两种对 G 1 的标号圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圶圵算法示例圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圸圶一个点不能连出两条杂边示例圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圹圷 X 圽圱, Y 圽地情形的讨论圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圱地圸 X 圽圱, Y > 圱或 X > 圱, Y 圽圱情形的讨论圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圱地圹 X > 圱, Y > 圱情形的讨论圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圱圱圱地 X 圽圱, Y 圽圱情形的讨论圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圱圱 List of Tables 圱得分统计圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圮圱圲圲

3 1 题意简述对于无向图 G 0 圽在 V 0, E 0 圩, G 1 圽在 V 1, E 1 圩我们称 G 1 是由 G 0 变换得到的, 当且仅当每个 G 1 的顶点和 G 0 的一条边一一对应 ; G 1 的一对顶点间有一条边, 当且仅当在 G 0 中的对应边有一个公共顶点已知 G 1, 求一个可能的 G 0, 或者宣告这样的 G 0 不存在 2 命题思路坃坯坤坥坃坨坥坦上有一道题 : 已知 G 0 圽在 V 0, E 0 圩 G 0 变换一次得到 G 1,G 1 变换一次得到 G 2,G 2 变换一次得到 G 3 求 G 3 的点数和边数其中 V 0, E 0 圱地地地 1 我们设 G i 圽在 V i, E i 圩最直接的想法是, 直接求一个合法的 G 3, 然后返回它的点数和边数这显然可以分成圳步第一步, 根据 G 0 求 G 1 ; 第二步, 根据 G 1 求 G 2 ; 第三步, 根据 G 2 求 G 3 不失一般性, 我们考虑如何根据 G 0 求 G 1 我们对 G 0 的边编号, 例如圱到 E 0 在 G 1 中建立 E 0 个点接着, 枚举两条边 e 1, e 2, 若 e 1, e 2 有一个公共顶点, 那么我们在 G 1 中,e 1, e 2 对应的点间连一条边容易看出, 这个做法的复杂度是 O 在 E 0 2 圩的如果直接执行本算法圳次, 算法的复杂度可能是 O 在 E 0 8 圩对给出的数据范围, 显然无法承受不过这个复杂度似乎无法达到注意到 E 1 有可能达到圂在 E 0 2 圩图在圱圩就指出了这样一种情形 E 2 看起来就很难达到圂在 E 1 2 圩, 更难达到圂在 E 0 4 圩了这是因为, 变换以后边数平方的图, 看起来不大可能由一个图变换而来什么样的图才能由一个图变换而来呢? 虽然如此, 不过这个算法的时间复杂度显然高于 O 在 E 0 2 圩, 因而我们不能直接使用这个算法另一种想法是直接计算点数和边数 1 命题者 Gennady Korotkevich. 圳

顶点的边对, 如图在圲圩 2 坃 d v 在圱圩坆坩坧坵坲坥圲场 G 2 中的点对应至 G 0 G 1 中的点对应 G 0 的一条边因而 G 2 的边, 对应于一对边对, 这两个边对共享一条边也就是说,G 2 的边,

4 坆坩坧坵坲坥圱场一个 E 1 圽圂在 E 0 2 圩的情形首先看如何根据 G 0, 求 G 1 的点数和边数显然 V 1 圽 E 0, 而 G 0 中凡是有一个公共顶点的边对, 会对 E 1 贡献圱改变枚举的对象, 考虑公共顶点 i 设点 i 的度为 d i 由于 i 连出的每对边, 给答案贡献圱因而 E 1 圽 v V 0 再来看如何求 G 2 的点数和边数显然 V 2 圽 E 1 G 2 中的点, 在 G 0 中对应一个共顶点的边对, 如图在圲圩 2 坃 d v 在圱圩坆坩坧坵坲坥圲场 G 2 中的点对应至 G 0 G 1 中的点对应 G 0 的一条边因而 G 2 的边, 对应于一对边对, 这两个边对共享一条边也就是说,G 2 的边, 对应于连通的圳条边有如图在圳圩所示的两种情况求 E 2, 可以分别考虑这两种情况对于第一种情况, 可以枚举图中绿色的边在 u, v 圩一条连着 u 的边, 一条连着 v 的边, 再搭配上边在 u, v 圩, 就对答案贡献一对于圴

5 坆坩坧坵坲坥圳场 G 2 中的边对应至 G 0 第二种情况, 可以枚举图中红色的点 v, 与 v 连着的圳条边对答案贡献一形式化地描述, 就是 E 2 圽 (u,v) E 0 在 d u 圱圩在 d v 圱圩圫 v V 0 3 坃 d v 结合这两个想法, 我们实际上解决了这个问题算法包含以下两步在圲圩圱圮根据 G 0 求一个合法的 G 1 这一步的时间复杂度为 O 在 E 0 2 圩圲圮根据 G 1 直接计算 G 3 的点数和边数这一步的时间复杂度是 O 在 V 1 圫 E 1 圩圽 O 在 E 0 2 圩本人在解决此题的过程中, 想到, 这个问题的逆问题是否可以解决呢? 于是本题就出现了 3 考查点本题是一道图论问题, 注意考察选手对图论知识的综合运用本题涉及了团补图二分图, 以及图的遍历等知识这些知识都是一个具有坎坏坉水平的选手应当掌握的同时, 本题需要选手深入细致的分析, 从而得到完整的解决方案圵

4 问题分析原问题变为逆问题后, 遇到的最直接的障碍就是坜谁对应谁圢已知的图是 G 1, 而 G 1 的每个点对应于 G 0 的一条边我们可以假设 G 1 的每个点 v, 对应于 G 0 的一条边 e v 如果我们把假想中的 G 0 标号,e v 连接着的是 x v 与 y v 那么, 相当于我们给 G 1 的每个点 v 带上两个标号在 x v, y v 圩在 x v 圽 y v 圩

6 4 问题分析原问题变为逆问题后, 遇到的最直接的障碍就是坜谁对应谁圢已知的图是 G 1, 而 G 1 的每个点对应于 G 0 的一条边我们可以假设 G 1 的每个点 v, 对应于 G 0 的一条边 e v 如果我们把假想中的 G 0 标号,e v 连接着的是 x v 与 y v 那么, 相当于我们给 G 1 的每个点 v 带上两个标号在 x v, y v 圩在 x v 圽 y v 圩而变换的要求, 相当于对任何相邻的两个 G 1 中的点 u, v, 以下圴个条件恰好满足一个 x u 圽 x v x u 圽 y v y u 圽 x v y u 圽 y v 而任何两个不相邻的点 u, v, 这圴个条件均不满足这样, 容易想到一个最简单的方法对含有 n 个点的 G 1, 每个点需要一对标号, 因而我们可以直接搜索每个点的标号是什么注意到最多只会有圲 n 个可以填的空, 因而, 至多只需要圲 n 个数之后, 我们可以检查一下搜索结果是否符合要求最朴素的检查方法, 即枚举两个 G 1 的点, 判断是否满足要求因而直接搜索的复杂度是 O 在在圲 n 圩 n n 2 圩的由于这个算法时间复杂度实在过高, 因而期望得分是地分这个算法未能解决问题的原因是, 它只对问题进行了大致的描述容易发现, 如图在圴圩所示的情形, 一张图可能有两种不同的标号, 但它们的效果完全相同这就说明, 搜索存在冗余坆坩坧坵坲坥圴场效果相同的两种对 G 1 的标号圶

7 改进方法便是, 对于效果相同的标号方式, 只搜索一次实际上, 我们只关心哪些数字相同, 而不在乎数字具体是几因而, 可以采取的搜索方法是, 记录之前用过几个数字, 对于当前的空位, 要么填上之前用过的数字中的一个, 要么写一个新的数字我们来计算这个算法最多会访问多少状态如果用 S 在 i, j 圩表示填 i 个空, 用了 j 个数字那么 S 在 i, j 圩圽 S 在 i 圱, j 圱圩圫 js 在 i 圱, j 圩 2 设 B n 圽 n i=1 S 在 n, i 圩 3, 那么这个算法的时间复杂度是 O 在 B 2n n 2 圩由于这个算法复杂度仍然很高, 因而期望得分仍是地分容易看出, 简单变换不改变连通性一张图可以分成若干连通块如果我们能处理清楚每一个连通块, 那么问题就得到了解决故下文中, 如无特别说明, 均只考虑 G 1 是一个连通块的情形注意到搜索结果需要满足要求, 而上述搜索方法在搜索过程中没有利用到这些要求因而可以考虑由此下手如果一个 G 1 的点被标为在 a, b 圩, 那么根据要求, 与它相邻的点的标号的一个数, 需要是 a 或者 b 这个优化, 可以使得搜索的状态数减少到 O 在圲 n 1 B n+1 圩再配合上一些显然的性质, 如同一点的圲个标号不能相同, 同一点的圲个标号的顺序无关, 可以使得这个状态数难以达到算法的复杂度降至 O 在圲 n 1 B n+1 n 2 圩期望得分是圱地分进一步考虑一开始, 选择一个 G 1 点 v, 直接标号为在 a, b 圩然后, 与 v 相邻的点的一个标号, 要么是 a, 要么是 b, 我们可以搜索这些点的一个标号接下来每一步, 选择一个只确定了一个标号的点, 搜索它的另一个标号有两种情形一种是新建一个标号, 另一种是选一个已经有的标号注意到选择已经有的标号, 最多的可能只有圱种这是因为, 选择已经有的标号, 只能从和它相邻的点中选而如果可选的有两种, 会导致不符合要求因而, 利用这个发现, 搜索的状态数只有 O 在圲 n 圩因而这个算法的时间复杂度是 O 在圲 n n 2 圩, 期望得分圲地分我们总是先搜索一个状态, 再判断是否可行而两个状态, 如果它们相同的部分很多, 重新判断一次就重复了对相同部分判断因而此处存在冗余如果我们边搜索边判断, 就能减少冗余利用这个方法, 可以使上述算法的复杂度降低至 O 在圲 n n 圩, 期望得分圳地分要更好地解决问题, 需要更进一步分析性质如图在圵圩所示, 抓取一个 G 1 点 v, 2 S(i, j) 是第二类 Stirling 数第二类 Stirling 数的定义及相关性质可参考 [2] 3 B n 是 Bell 数 Bell 数的定义和性质可参考 [3], 这个数列的前几项可以在 [4] 看到圷

8 坆坩坧坵坲坥圵场算法示例它在 G 0 中是一条边, 假设两端点分别为在 a, b 圩在 G 1 中和 v 相邻的点, 在 G 0 中对应的边, 要么连着 a, 要么连着 b 根据简单变换的规则, 凡是在 G 0 中连着同一个点的边, 在 G 1 中都有边相连, 因而这些在 G 0 中的共点边, 在 G 1 中形成一个团因此,v 的邻域 N 在 v 圩的导出子图有最多两个团, 外加一些坜杂边圢了 4 了对于杂边, 由图在圶圩可以观察出, 一个点不能连出两条杂边否则就会出现重边注意到 N 在 v 圩的导出子图 G 1 坛 N 在 v 圩坝最多含有两个团如果取一个补图, 就是二分图 4 要说明这一点, 不妨假设连出杂边的点是 u, 其编号为 (a, t), 与其通过杂边相邻的点的编号必有一个标号是 t 而由于这些点都与 v 相邻, 而且与 u 不同属一个团, 因而必有一个标号是 b 故与 u 通过杂边相邻的点的标号只能是 (b, t) 圸

坆坩坧坵坲坥圶场一个点不能连出两条杂边示例在 N 在 v 圩中随便选一个初始点 u, 让它的一个标号是 a 在补图中, 利用二分图染色法, 尝试确定每个点的一个标号是 a 还是 b 如果不是二分图, 说明无解否则一些点会被确定图根据标号是 a 还是 b, 被分为 X, Y 两部接下来看没有被确定的点分几种情况讨论 X 圽圱, Y 圽地即没有点的一个标号是 b 这是一种十分特殊的情况

9 坆坩坧坵坲坥圶场一个点不能连出两条杂边示例在 N 在 v 圩中随便选一个初始点 u, 让它的一个标号是 a 在补图中, 利用二分图染色法, 尝试确定每个点的一个标号是 a 还是 b 如果不是二分图, 说明无解否则一些点会被确定图根据标号是 a 还是 b, 被分为 X, Y 两部接下来看没有被确定的点分几种情况讨论 X 圽圱, Y 圽地即没有点的一个标号是 b 这是一种十分特殊的情况这意味着, 在 G 1 坛 N 在 v 圩坝中, 没有一个点与 u 相邻应当考虑换一个点作为初始点如果无法找到在 G 1 坛 N 在 v 圩坝中度大于地的点, 说明在 G 1 坛 N 在 v 圩坝, 任两点都相邻亦即,N 在 v 圩是一个团如果未确定的点数大于等于圲, 说明所有的点都应该有标号 a 这是根据对杂边的观察可以观看图在圷圩来更加清晰地认知 X 圽圱, Y > 圱, 或 X > 圱, Y 圽圱即有一部只有圱个点, 剩下的一部有超过圱个点, 如图在圸圩所示, 那么未确定的点应该归大于圱个点的那部 X > 圱, Y > 圱即每部都大于圱个点如图在圹圩所示, 如果还有未确定的点, 就无解 X 圽圱, Y 圽圱这个情况表明每部都恰有一个点图在圱地圩显示了此情况如果未确定的点大于圲个, 那么无解这样未确定的点最多圲个我们枚举它们属于哪一部然后采用坂坆坓, 确定其余点的标号最后检查是否合法即可这里说明在算法一开始抓取点 v 的时候的问题如果抓取度数最小的点, 是没有问题的如果这个点的度数是 d, 容易看出,nd 圲 m, 因而 d 2m n 如果随意抓取点是否有问题呢? 事实上我们可以用一些不等式来确定范围我们希圹

10 坆坩坧坵坲坥圷场 X 圽圱, Y 圽地情形的讨论坆坩坧坵坲坥圸场 X 圽圱, Y > 圱或 X > 圱, Y 圽圱情形的讨论望补图的边尽量多, 而原图的边尽量少, 因为我们有两个团, 所以边根本少不到哪里去亦即 1 2 x 在 x 圱圩圫 1 2 在 d x 圩在 d x 圱圩 m, 这样 d 圲 m, 也就是说, 度数不能太大这个观察使得求补图的时间复杂度是 O 在 m 圩的接下来说明如何坂坆坓坂坆坓的目的是确定 G 1 每个点的标号, 代表 G 0 中对应的边一开始所有点的标号都形如在圿, 圿圩被抓取的点标号已确定与被抓取点相邻的点, 标号确定了一半, 有的是在 a, 圿圩, 有的是在 b, 圿圩每一次, 选一个标号已经确定了一半的点在 x, 圿圩查看是否存在与它相邻的, 标号确定了一半的点在 y, 圿圩如果存在, 那么这圱地

完全未确定的点在圿, 圿圩, 改为在 z, 圿圩这样, 就能在 O 在 n 圫 m 圩的时间内确定每个点的标号了最后说明如何检查合法性首先,

11 坆坩坧坵坲坥圹场 X > 圱, Y > 圱情形的讨论坆坩坧坵坲坥圱地场 X 圽圱, Y 圽圱情形的讨论两个点的标号都应该是在 x, y 圩与该点相邻的, 完全未确定的点在圿, 圿圩, 改为在 y, 圿圩否则, 我们选一个新的数 z, 将其标为在 x, z 圩与该点相邻的, 完全未确定的点在圿, 圿圩, 改为在 z, 圿圩这样, 就能在 O 在 n 圫 m 圩的时间内确定每个点的标号了最后说明如何检查合法性首先, 我们检查是否有重边, 自环接着, 我们检查求得的 G 0 生成的 G 1 的边数这一步, 只要计算每个点的度数 d i, 然后即是答案圱圱坃 2 di

12 最后, 我们检查在 G 1 中相邻的两个点在 G 0 中对应的两条边是否在 G 0 中有公共顶点这是这个问题的参考解法, 其时间复杂度是 O 在 n 圫 m 圩, 期望得分圱地地分 5 数据生成方法如何生成本题的数据呢? 如果直接随机生成 G 1, 那么将会有很大概率出现无解一种很简单的方法是, 随机生成 G 0, 然后, 将 G 0 变换成 G 1 这种方法虽然十分简单, 但不能完全体现本题的复杂性如果在算法中漏考虑了一些情况, 仍然可以通过随机生成的数据解决的办法是, 本人手画了一些, 和用程序生成了一些特殊情况的数据, 使得需要考虑到特殊情况这些数据并不是很大用随机的方法生成了数据之后, 我们对其中大部分数据配上圱到圲组特殊数据, 这样就使得选手需要充分考虑了各种情形才能够通过本题除了使用随机方法生成 G 0, 本人还考虑了一些特殊的图, 例如链环毛毛虫树环套树二分图团等部分测试数据的 G 1 就是由这样的图生成的 6 选手得分统计本题对国家队候选队员进行了测试, 得分统计如表在圱圩所示分数圱地圵地圷地人数圲圱圱坔坡坢坬坥圱场得分统计本题的平均分大约为圱圲圮圷分 7 后记集训队测试后, 顾昱洲同学发现, 变换后的图有一个名字, 叫做坌坩坮坥坧坲坡坰坨他给圱圲

13 出了一个链接 5, 和一篇文章的名称 6 这使本人大为惊讶在链接中, 提到了有人曾对此进行研究, 并以线性时间解决了它, 但没有指明具体的做法这篇文章, 虽然有名字, 但本人和他都没有找到免费的查看或下载的途径, 因而其做法不得而知因而无法比对本文所指出的做法与其做法的异同本人正在寻求该论文, 探讨该问题有否更好的解法 Roussopoulos, N. D. (1973), A max m,n algorithm for determining the graph H from its line graph G, Information Processing Letters 2 (4): 圱圳

14 References 坛圱坝 February 2012 Cook-off Problem Editorials 坛坅坂圯坏坌坝圮 wiki/february-2012-cook-problem-editorials 圮坛圲坝 Stirling number 坛坅坂圯坏坌坝圮坛圲地圱圲圭圳圭圲圴坝圮 Stirling_number 圮坛圳坝 Bell number 坛坅坂圯坏坌坝圮坛圲地圱圲圭圳圭圲地坝圮 number 圮坛圴坝 Bell or exponential numbers: ways of placing n labeled balls into n indistinguishable boxes. 坛坅坂圯坏坌坝圮坛圲地圱圲圭圴圭圱圷坝圮圮圱圴

15 Index 坂坆坓圬圱地分解二分图圬圹变换的要求圬圶对几种情形的讨论圬圹抓取点圬圹杂边圬圸根据 G 0 求 G 1 圬圳检查合法性圬圱圱圱圵

16 Appendices A flare 完整题面坔坩坭坥坌坩坭坩坴场圷坳圬坍坥坭坯坲坹坌坩坭坩坴场圱圲圸坍坂这是一个很有趣的想法, 如果熊是蜜蜂, 他们会将他们的巢建在树下而且如此的话 ( 如果蜜蜂是熊 ), 我们就不用爬上楼梯了这是小熊维尼的一首充满抱怨的歌你是否曾经想过, 有些关于无向图的问题, 如果把边看成点, 点看成边, 会更容易解决? 这道题目正与此有关假设有一张无向图 G 0, 让我们对 G 0 执行一次简单变换, 来得到无向图 G 1 G 1 满足, 每个 G 1 的顶点和 G 0 的一条边一一对应,G 1 的一对顶点间有一条边, 当且仅当在 G 0 中的对应边有一个公共顶点可能与你猜测的不一样, 本题给出了 G 1, 求一个满足条件的 G 0 Task: flare Input: stdin 输入的第一行含两个数 n, m, 代表点数和边数接下来 m 行, 每行有两个数 a, b 在圱 a, b n 圩, 表示 a, b 间有一条边保证每条边连接了两个不同的顶点, 每对顶点最多有一条边相连 Output: stdout 如果这样的 G 0 不存在, 输出坜圭圱圢否则, 输出 n 行, 每行两个数, 代表 G 0 的一条边的两个顶点 G 0 的第 i 条边对应于 G 1 的顶点 i 输出需要满足, 每条边连接了不同的顶点, 每对顶点间至多只有一条边你可以自行给顶点标号, 但顶点的标号需要是正整数, 而且不应超过圱地 9 圱圶

17 Sample Input Sample Output Hints 样例的图是坜三角形圢 ( 三个点, 两两间均有边 ) 容易看到坜三角形圢简单变换后仍是坜三角形圢当然, 样例的解并不唯一 Constraints 对圱地圥的数据, 圱 n 圱地对圲地圥的数据, 圱 n 圱圵对圳地圥的数据, 圱 n 圲地对圵地圥的数据, 圱 n 圱地 2 对圷地圥的数据, 圱 n 圱地 3 对圱地地圥的数据, 圱 n, m 圱地 6 B Glossary of graph theory 图由点集 V 和边集 E 构成点对在 u, v 圩称为边图 G 的点集可以用 V 在 G 圩或 V 来表示一张图的阶就是点的个数, 表示成 V 在 G 圩图 G 的边集可以用 E 在 G 圩或 E 来表示一张图的大小就是边的数目, 表示成 E 在 G 圩图 G 的补图 G, 和 G 有相同的点集, 而边集为 { 在 x, y 圩在 x, y 圩 E 在 G 圩 } 一个点 v 的度 d G 在 v 圩是与 v 有关的边的数目一张图的总度数等于边数的两倍图 G 的团是两两有边的点集 C Usage of the program 本题给出的参考程序具有多种功能下面介绍在坌坩坮坵坸平台下的用法圱圷

18 获得本题的解运行./flare, 然后用屏幕输入数据, 程序将在屏幕输出结果如果想从 <infile> 中读取文件, 输出到 <outfile> 中, 可以用命令./flare < <infile> > <outfile> 作为清橙测试器的比较程序清橙测试器会执行./flare <in> <out> <ans> <log>, 圴个参数分别是读入文件, 选手输出文件, 标准输出文件, 结果文件检查答案是否合法对一组输入输出文件 <infile> <outfile>, 运行./flare -check <infile> <outfile>, 将判断输出文件是否能对应输入文件你也可以运行./flare -check <number>, 来检查文件名为 flare<number>.in 和 flare<number>.out 生成数据运行./flare -make <number>, 将生成一组名为 flare<number>.in 和 flare<number>.out 的数据圱圸

IDEO_HCD_0716

IDEO_HCD_0716 IDEO HCD Toolkit Tencent CDC ...? Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC