信息学学习笔记（1）：可怕的图论

墨蓝 2022-04-25 05:04 177阅读 0赞

到了2019年3月份，我学算法已整一年。这个时候我觉得应该看一下提高组的复赛题了。NOIP 2018提高组初赛的题去年看过，比普及组难了不少，但是整体还好，没达到非常难的程度。复赛题我没做过，但是想必会难很多。

通常而言，难度是逐题递增的，最后一题就是最难的。不过少数情况下是例外，这种情况下出题者会故意把压轴题调到倒数第二题的位置，比如NOIP 2018年普及组的复赛题就是如此。

NOIP 2018年提高组的最后一题最难，题目名是“保卫王国”。题目倒是很容易看懂。不幸的是，看完之后，除了看出来是考察图论外，我几乎毫无思路。图论是数据结构里的最难的一章，没有有之一。整个数据结构，其他的内容我都很熟悉，唯独图论仅仅学了点皮毛。

既然自己没有思路，那就直接看别人的答案。遗憾的是，看了整整两天，也没看懂别人的思路。倒是在这个过程中，了解到涉及的知识点有LCA（最近公共祖先）、倍增、树链剖分 + 动态规划的方式实现。倍增和树链剖分对我来说是全新的概念，以前听都没听过。

这样的话，这题就不能继续做了，要先把基本的最近公共祖先学了。无论是学什么新的算法，首先要学的就是暴力法，暴力法最简单，理论上可以用来解决所有的问题。遗憾的是，暴力法天生效率低，只要数据量一大，暴力法很容易超时。学了暴力法之后，感觉对求最近公共祖先的方法有了基本了解，就继续学倍增方法，结果发现倍增不太难。

接下来就是树链剖分。树链剖分的原理也不难，但是看代码的时候，发现用到了build(), pushup(), pushdown()等函数，这些看起来像是用到了别的知识。几经查询，发现原来是一个新的知识点：线段树。

线段树是一种很奇妙的思路。看到线段树的时候，我想起不止一名学生曾对我说过：算法太可怕了！很多奇妙的算法，前辈们不知道是如何发现的，但毫无疑问是付出了长时间的汗水才研究出来的，等到你去学的时候，你就会发现思路精妙无比。有些算法思想确实太可怕。

学完线段树再回到树链剖分，理解起来基本就没有问题。

然后再回过头来看“保卫王国”的答案，这个时候深入思考加反复调试，终于理解过来。

理解了“保卫王国”的解法后，我回想起来，在这些过程中，我发现图的构建方式用了一种枚举边的方式，具体是倒序枚举。我以前不知道这种方式，是通过无数次模拟才理解过来的。我猜测这也是一个专门的知识点，几经查询发现这个叫做“链式前向星”，是在“前向星”的基础上优化过来。“前向星”对我来说，也是一个全新的名词。“链式前向星”和“前向星”都是图的存储方式，有些数据结构的教材里面并没有提及。在这之前，图的存储方式，我只能理解邻接矩阵这一种，邻接表理解得并不透彻。于是把几种常见的图存储方式都学了一遍，最终整理出五种：邻接矩阵，邻接表（数组实现）、邻接表（向量实现）、前向星和链式前向星。

至此，感觉自己图论终于有所了解了。前后用了一个月的时间。这一个月的时间里我几乎没做别的事。整个过程是苦不堪言的，用小朋友们的话说就是：算法太可怕了！

我也明白了，为何有些人在学习信息学的过程中，学着学着就放弃了。因为算法确实非常难，有些人碰到了一些大山，久久翻不过去，就丧失了信心。而那些能坚持翻山越岭的人，有机会不断看到新的风景。

> 了解少儿编程、信息学竞赛请加微信307591841或QQ群581357582  
> ![信息学竞赛公众号.jpg][.jpg]

[.jpg]: /images/20220210/6bd0089401c14bb688eb37eac8a757e1.png