第十章满分试卷

里出奇地安静，只有时不时地枪毙试卷的声音。今年的数学难度系数大幅度大于往年，文雨看了一上午，超出一百三十分的没有一个。而且以她的角度来看，她也表示理解，毕竟这么超难的题目，自己一个研究生来做的话，多半也会黄。尤其最后一道，题目的开放性之大，让人无从着手。

题目的大意是：给出九个城市之间的距离，求从任意城市出发，遍历各城市各一次的最短路径，不能用穷举法。

这就是世界上鼎鼎大名的旅行商问题，要得出解，就必须对问题有着极强的抽象能力和分析能力。抽象，就是建立模型，分析，也就是找出时间复杂度最小的最合理的算法。吃午饭的时候，文雨又把这道压轴题前前后后思索了一遍，还是没能解出来。

下午，阅卷继续，沉闷的空气压得文雨呼吸都不爽快，尤其是看到成绩，文娱暗暗庆幸自己高考没有生在现在这几年。一张张不及格的试卷看得她心烦意乱，老教授眼睛里那复杂，猥琐的目光也让她浑身不自在。

终于最后一张一卷了，文雨大吸了一口气，有一种立刻就要解脱了的快感。最后一张试卷，也就是第一个交的试卷，这类同学，在高考考场上一般都是丝毫不重视考试，仗着家里有关系，随意糊弄几下试卷，完了走人的那种。想到这，文雨也漫不经心地随意瞄几眼。

出乎意料，字迹很清晰，条理很清楚，那一条一条跳跃性很强的运算看得她一愣一愣的。文雨心理不服气，想着法儿给试卷挑毛病，妄图扣点分。她的脾气一直是这样，有点知识分子家庭独生子女的娇惯气。结果她失望了，直到最后一道题目之前，轰轰烈烈的纠错大行动宣告失败。虽然失败，她的心里却又有着一种莫名的希望，这是硕果仅存的一张卷，前面的一百三十分一分也没有跑。光这一百三十分，就已经是全市数学单科最高分了。不知道最后一道大题会做的怎么样。

怀着满腔的好奇，翻到了最后一页。一看答案的第一行，文雨就乐了。只见试卷第一行就大言不惭写着：此题解题方法属于笔者原创，如有雷同，不甚荣幸，如有错误，纯属抄袭。

看来这家伙对自己的解题能力蛮自信的嘛。对的就是自己做的，还不准别人抄袭，错的就是别人做的，自己抄袭的。真是圆滑得像条泥鳅。

文雨斜着头，微笑着开始看解题步骤。

答题者是采取了二分图的数据结构，然后自己引入－饱和点，_交错路，_可增广路三个概念。

算法的轮廓是首先置为空，然后找

本章未完，请点击下一页继续阅读！ 第2页 / 共4页