第69章 复试

转眼间，就到了七月十五日，也是首都青少年信息学奥林匹克联赛NOIP复试的日子！

复试的考试地点依旧在首都首都邮电大学，稍有差别的是，因为是上机测试，考试地点不在教学楼，而是在新建成的多媒体教学实验楼。

这个时代正在流行所谓的多媒体概念，实际上就是电脑的声音图像效果变得越来越强大，更加被重视起来了。多媒体教学实验室，其实就是有着电脑、投影和音响的教学室。

陈季常还是第一次走进这么高科技十足的教学楼，顿时被眼前的景象深深吸引。

走进宽敞明亮的教室，首先映入眼帘的是一块巨大的屏幕，它几乎占据了整面墙壁。屏幕两侧，一对高大的音响静静地伫立，仿佛随时准备播放出震撼人心的声音。教室中央，整齐地摆放着一排排课桌椅，每个座位前都配备了一台小巧的显示器，下面是一个无盘工作站，方便学生实时操作。

教室的角落里，一台台沉重的服务器主机堆叠在一起，它们是整个多媒体教室的“心脏”，为整个系统提供着源源不断的计算力。这些服务器主机虽然看起来有些笨重，但在当时却代表着最先进的技术。那些无盘工作站都是需要这些服务器分配计算存储资源才能使用。

教室的灯光柔和而明亮，给人一种宁静而舒适的感觉。空气中弥漫着一种淡淡的电子产品特有的气味，这是那个时代特有的味道。

陈季常按照教室管理员的指引，在自动鞋套机上踩下去，让自己鞋上裹上一层薄薄的塑料薄膜。这就是所谓的一次性鞋套。

这个年代，大家都认为计算机是一种非常昂贵而娇气的东西，要防尘防高温还得防静电，所以进入微机室是一定要穿鞋套的。这是一项铁的规定，即使是学校领导也不能例外。

考试铃声响起，监考老师打开投影仪，将考题内容投射到屏幕上时，开始讲解考试内容和考试要求。所有考生目不转睛地盯着屏幕，听着老师的讲解，生怕错过任何一个细节。

考试总共三个小时，幕布上显示三道大题，全部都是上机编程题。

考生需要打开自己面前的无盘终端，输入自己的考号进入独立的虚拟磁盘空间。

在这个虚拟磁盘里，有BASIC、PASCAL和C++三种编程软件，考生可以任选一种进行编写程序。最终程序文件和源代码文件按照要求，放置在由考号组成的目录之下就行了！当然，如果始终编译通过不了，只放半成品源代码文件也是有分的，但肯定分不高了。

陈季常首先按照老师的提示，一步步进入自己的虚拟磁盘空间，打开C++编程软件后，开始仔细阅读幕布上的考试题。

三道题是这样的：

“

题目一：最长不下降子序列（Longest Non-Decreasing Subsequence， LNDS）

问题描述：

给定一个整数序列，找出并输出该序列的最长不下降子序列的长度。一个不下降子序列指的是序列中从左到右元素逐渐增大或相等的子序列。

输入：

第一行包含一个整数n（1 <= n <= 10^5），表示序列的长度。

第二行包含n个整数，表示给定的整数序列。

输出：

输出一个整数，表示最长不下降子序列的长度。

题目二：最短路径问题（Shortest Path Problem）

问题描述：

给定一个带权无向图，求从起点s到终点t的最短路径长度。

输入：

第一行包含三个整数n， m， s， t（1 <= n <= 10^4， 1 <= m <= 10^5， 1 <= s， t <= n），分别表示图中的顶点数、边数、起点和终点。

接下来m行，每行包含三个整数u， v， w（1 <= u， v <= n， 1 <= w <= 10^9），表示顶点u和顶点v之间有一条权值为w的边。

输出：

输出一个整数，表示从起点s到终点t的最短路径长度。如果无法到达，则输出-1。

”

陈季常看完前两道之后，简直要笑出声了，这两题不仅有把握，而且不久前才练过类似的。简直就是送分题！

不过第三题的确有难度！

“题目：网络流中的最大流问题（Maximum Flow Problem in Network Flows）

问题描述：

给定一个有向图，图中的每条边有一个容量限制。图中的两个特殊顶点s和t被称为源点和汇点。网络流问题是指寻找一种方式，使得从源点s到汇点t的流量达到最大，同时满足以下条件：

对于图中的每条边，其通过的流量不能超过其容量限制。

对于图中的非源点非汇点，流入该点的流量等于流出该点的流量（即流量守恒）。

输入：

第一行包含四个整数n， m， s， t（1 <= n <= 1000， 1 <= m <= 50000， 1 <= s， t <= n），分别表示图中的顶点数、边数、源点和汇点。

接下来m行，每行包含三个整数u， v， c（1 <= u， v <= n， 1 <= c <= 10^9），表示从顶点u到顶点v有一条容量为c的边。

输出：

输出一个整数，表示从源点s到汇点t的最大流量。

”

陈季常反复阅读了几遍，思索了十分钟，才终于弄明白！这个问题是网络流问题，需要使用Ford-Fulkerson算法、Edmonds-Karp算法、Dinic算法等高级算法来求解。这些算法涉及到深度优先搜索、广度优先搜索、图的分层等复杂技术，因此这个问题对参赛者的算法设计和实现能力有相当高的要求。

好在陈季常思索一番，还是有把握做出来的！

就这样，陈季常双手在键盘上啪啪啪飞快敲击，仅仅用了一个小时，就把前两道题全部搞定。编译运行后，也是一切正常。

陈季常将这两题的源代码文件和编译执行文件都上传到考试提交目录后，开始一边思索一边尝试编写第三题的程序。

陈季常最终决定用Relabel-to-Front算法来解决这个难题。Relabel-to-Front算法是Push-Relabel算法的一个变种，它通过维护一个“front”集合（即距离汇点最近的顶点的集合）来优化push操作，从而提高算法的效率。Push-Relabel算法呢？这是一种基于预流推进（Preflow-Push）技术的算法。它首先将所有的边都尽可能地推向汇点，形成一个预流（Preflow），然后通过一系列的“push”和“relabel”操作，使得流量守恒并且满足容量限制，最终得到最大流。

有了思路，一切就好办多了。就这样，陈季常修修改改，删删补补，花了一个来小时，终于将这一道难度不小的题目做了出来。

编译运行，结果完全符合要求。陈季常长舒一口气，这下总算是搞定了！

正要提交，他突然想起赵老师叮嘱的一句话，“如果有时间有精力，尽量把代码写得清晰明了，增加详尽的注释，这样会减少扣分的几率！”

陈季常连忙打开自己的第三题源代码，再一次审视起来。果然，由于边思索边修改，又进行缝缝补补，代码的可读性的确不怎么样！

发现问题，修改就简单多了。陈季常双手如风，飞快地将一行行代码列齐规整，然后再在后面增加大段注释，使得批卷老师一眼就能看得清清楚楚，明明白白，不用猜来猜去，揣摩这段代码是什么意思！

陈季常又花了二十分钟将代码调整完毕，再次进行编译，顺利通过，运行程序一切正常。

他这才长舒了一口气，将第三题的源代码和执行文件上传到提交目录。

一切都搞定，陈季常举手示意自己交卷。监考老师过来，检查了一下他提交的文件都是正常无损，于是将文件倒入服务器存储空间。这才算正式结束，陈季常终于可以离开了！

这时候，已经距离考试结束不到半个小时了！

陈季常走出考场，见到等候的赵老师，有些惊讶地发现他身边的考生还不少，这些自然都是提前交卷出来的。

陈季常心里一紧，想着大牛这么多，都比我速度快，这下可糟了！

赵老师见陈季常过来，连忙急切地问：“怎么样？陈季常同学，做出来几道？”

“啊？”陈季常有些懵，反问道：“老师，不是三道都得做吗？”

“三道你都做出来了？”赵老师一听，兴奋不已，追问道：“都编译通过了吗？执行结果都对吗？”

陈季常点点头，“都做出来了！也都编译通过了，结果也都没问题。大家不都这样吗？”

“呵呵！你做出来就好！”赵老师很开心，也就不在乎他最后那句凡尔赛了！

一旁有考生听了，惊讶不已，“这位同学，最后一道大题你也做出来了？那道题太难了，我看了四十分钟硬是不知道如何下手，干脆放弃了！”

另一个考生也追问道：“这位同学，你是用什么算法做的？我用Edmonds-Karp算法，做来做去做不下去，结果只等交了个半成品源代码！”

陈季常挠挠头，说：“哦，我是用Relabel-to-Front算法做的。”

“Relabel-to-Front算法？”对于这个陌生的名词，周围的考生都是一片大眼瞪小眼！

赵老师连忙解释一句：“Relabel-to-Front算法是Push-Relabel算法的变种，这个算法比Push-Relabel算法效率更高一些。呵呵，其实考试用什么算法都行，只要能做出来，效率高低并不关键！”

Push-Relabel算法还是有不少人听过的，但会运用的也是寥寥无几！