贪心算法啊，以前老是以为它没什么技术含量，上不了台面。长时间下来，也就养成了“不可能是贪心这么简单”的思维习惯，遇到问题时几乎不会往贪心的方向想。

    可是谁料到最近一下就被我碰到了两道贪心题，改变了我对贪心的观点。其中一题我在上一篇就讲过了，是 2008 年 TUDPC 的第 E 题。还有一题就是 PKU 3110。

    题意是说有 N 门考试（N ≤ 50,000），各门考试的日期跨度大约不超过 73,000 天（这个故事好像有点不符合现实，但是毕竟是题目嘛）；每门课都需要一天的时间复习；两门课不能在同一天复习；有考试的日期不能复习功课；每门考试都有一个复习的时间下限，即复习的日期不能早于考试的前若干天，否则到考试时会忘掉；如果要通过所有考试，问可以最晚开始复习的日期（即第一个复习的日期要尽量的晚）是哪天。

    我开始还在往最大匹配上想，每门考试是左边的一个节点，每个日期是右边的一个节点，每门考试对应有限的几个日期，每个日期只能有一门考试。整个模型乍看有点像样，但是看看数据规模就知道不可能了。况且这样算不出最晚开始复习的日期。

    后来得知了可以用贪心解决，算法很简单：把所有考试从晚到早排序，从最晚的考试日期开始倒数；如果当天有考试，则把这些考试的复习时间下限放进一个优先队列；如果当天没有考试，则从优先队列里取出下限最晚的一个，把它复习掉；如果从优先队列里出来的这个时间下限已经比当天晚了，则无解。

    不难证明，这样得到的是最优解。假设一天没有考试，优先队列里时间下限最晚的一门考试是 A，但是当天没有复习这一门，而是复习了下限较早的考试 B。如果这样最终得到了最优解，那么，即然 A 的下限比 B 的晚，则互换 A 和 B 的复习日期是合法的，而且同样是最优解。也就是说，以上算法可以得到最优解。□

    以上这两道贪心的题目都是和工作流程之类的沾点边的，看来以后碰到这种题的时候要多长个心眼了。

    真的是好久没写 BLOG 了。现在只有最后的几个月为我最后一届 ACM 比赛而奋斗了，所以我想尽量多做几道题。上星期又是一年一度的复旦、东华、上大和少科站的练习赛。一连比了两场，我们队都是做出 6 题。题目都比较简单，但是有几道比较难的题，我觉得确实出得挺好的。

    第一场比的是 TUDPC 2008 的题目，共 8 道题，我就挑几道稍微难一点的回忆一下吧。

    D. Rain on your Parade

    看似不难，是典型的二部图匹配，左、右各 3000 个点，我觉得用匈牙利算法应该过得了。这道题是我的两个队友负责的，我没有过问。它们却一直 TLE，原因不明。当时他们一直在置疑匈牙利算法能不能应付得来左、右各 3000 个点的复杂度，我说我也不知道更快的算法。事后我也用匈牙利算法打了一遍这道题目，我决得并不慢。奇怪……

    E. Olympic Games

    有 50,000 个整数区间，问最多能选出几个，使它们两两不相交（允许两个区间的首、尾相连）。如 [1, 3]、 [2, 5] 和 [3, 4] 这三个区间，最多可以选出 [1, 3] 和 [3, 4] 这两个区间是不相交的。

    我的队友一下就想到了最大上升子序列（LIS），我一听有道理，正好我有 O(N logN) 的 LIS 代码，于是我就负责这道题了。可是这不是单纯的 LIS ，因为每个区间不是单纯的比大小，如果两个区间有相交或包含的关系，那该认为谁比较小？

    其实是这样的，通常的 O(N logN) 的 LIS 算法是用一个数组 T[] 记录长度为 1 ~ L 的上升子序列（IS）的尾巴的位置，L 是目前找到的最长的 IS 的长度。对于每个数组元素 a[i]，都用二分搜索找到最大的 x，满足 a[ T[x] ] < a[i]；也就是说，找到最长的尾巴比 a[i] 小的 IS；那么此时 a[i] 就是新的长度为 x + 1 的 IS 尾巴，或者说 i 是新的 T[x + 1]。

    但是这道题目不是说找 LIS，而是要构造一个 LIS，所以要先把所有区间递增排序，按区间的头部（左边界）递增，头相同的尾巴递增。然后再找 LIS。问题在于二分搜索这一步，就算找到了最大的 x，满足 a[i] 可以跟在 a[ T[x] ] 后面，此时 i 也不一定是新的 T[x + 1]。必须要 a[i] 的尾巴在原来的 a[ T[x + 1] ] 前面，才更新 T[x + 1]。

    举例说，a[i] = [3, 5]，找到了 a[ T[x] ] = [2, 3]，此时 a[i] 可以跟在 a[ T[x] ] 后面；但是如果原来的 a[ T[x + 1] ] 是 [3, 4]，它的尾巴在 [3, 5] 的前面，显然把 [3, 4] 作为 T[x + 1] 更有可能找到更长的解，所以此时不能更新 T[x + 1]。比赛时我就是没注意到这一点，吃了好几个 Wrong Answer。幸好后来我们想到了另一个算法，原来这道题可以贪心解的，如下。

    首先仍然是要把所有区间递增排序。假如已经找到了前 i 个元素的最优解，它的最后一个元素是 a[i]，此后的每一步都可以保证最后得到最优解：

• 如果 a[i + 1] 的头可以跟在 a[i] 的尾巴后面，则前 a[i + 1] 个元素的最优解当然就是以 a[i + 1] 结尾。
• 如果 a[i + 1] 的头不能跟在 a[i] 的尾巴后面，或者说 a[i + 1] 和 a[i] 有重叠，则再分两种情况（别忘了已经是排好序的，a[i + 1] 的头不会在 a[i] 的头前面）：
  • 如果 a[i + 1] 包含于 a[i]，则与 a[i + 1] 冲突的区间肯定更少，所以此时舍去 a[i]，保留 a[i + 1]。
    
  • 如果 如果 a[i + 1] 不包含于 a[i]，也就是说 a[i + 1] 的尾巴在 a[i] 的后面，则之后与 a[i] 冲突的区间肯定比 a[i + 1] 少，所以此时舍去 a[i + 1]，保留 a[i]。

    如此一来，每一步就可以保证总体的最优解。走许多弯路后，我们总算把这题 AC 了。

    G. Robotic Invasion

    这可以算是这套题里最难的一道吧，比赛当场也很少有人碰。赛后我才想到是动态规划，题目确实出得不错。说是有一个 100 × 100 的方格地图，其中有一些格子是墙，不能走上去；有一个起点和若干个终点，走到任意一个终点都算到达目标；给出一条指令，是一个由上、下、左和右组成的字符串，表示一条路径，长度最多 100，但是它不一定能从起点走到终点；现在需要修改这条指令，使得指令长度不变，而且可以走到目标；如果走到指令的一半就已经到目标了，则后半部分指令可以被乎略；如果有多个解，则输出满足下列条件的解： a. 修改的字符数最少。 b. 如果还有平局，则输出最先到达目标的指令。 c. 如果还有平局，则输出字典顺最先的指令。一看题目要求就挺吓人的吧，还好题目中的数据规模提示了我，令我发现是 DP。

    DP 的状态是这样的，需要三个数组： minChange[i][j][k]、 minTime[i][j][k] 和 newCmd[i][j][k]。 [i][j] 表示当前位于的格子，[k] 表示进行到了指令的第 k 个字符； minChange 表示从这一步开始的最优解需要改变后面指令的几个字符； minTime 表示从当前步开始的最优解离目标有几步； newCmd 表示最优解的当前这一步的指令是什么字符。有了状态，相信算法已经很清楚了吧，我就不多说了。

    这套题其余都是水题，连我们这种队都能秒杀，也就没什么好说的了。

    第二场比赛比的是 2007 年 Pacific Northwest 赛区的题目（好像是美国的某个赛区），今年浙江省某比赛的一场热身赛也引用了这套题目。让我也来回忆一下其中一些有意思的题目。

    B. Missile Command

    最少有人做出来的一题，不仅比较综合，而且题目比较难读懂。我们当时没碰，但是很高兴赛后我做出来了。说的是二维坐标系中，有最多 20 颗导弹从空中的（y > 0）某些点射出；导弹都是均速直线运动；各颗导弹的出发点、出发时间、运动方向和速度各不相同；导弹到达地面（y = 0）就算击中目标；防御方向空中发射了最多 20 颗高射炮，每颗高射炮于不同的时间在空中的不同点爆炸；爆炸呈圆形，持续 2 秒钟，圆的半径 r 服从时间 t 的函数 r = sqrt( 1 - (t - 1)² )，也就是说半径随着时间从 0 增至 1，又降至 0；如果导弹碰到了爆炸区域，则被阻挡。问最少采用其中的几颗高射炮，就足以阻挡最多的导弹。

    可以看出数据规模很小，是典型的搜索题，要找出最少的子集，让它们能覆盖整个全集。搜索之前需要几何的预处理，需要解一元二次不等式来判断各条直线和各个圆的相交。另外，题目还有一些歧义的地方，使过题更加困难：

• 即使是向上飞的导弹，虽然它不会击中地面，但是也要尽可能阻它。也就是说，如果一颗高射炮只挡住了向上飞的导弹，不要认为它是多余的。
• 题目中说“爆炸区域的半径为 0 时无法阻挡导弹”，这是个晃子，其实这种情况不会出现。因为通过求导可以知道，sqrt( 1 - (t - 1)² ) 在 t = 0 和 t = 2 处的斜率都是无穷大。也就是说，圆的半径在一开始和最后的变化都是很快的。一颗导弹不可能在一开始位于圆心，而后一瞬间立即飞出圆外；也不可能本来一直在圆外，只在最后时刻到达圆心，因为它的速度没有圆的半径变化得快，除非导弹的速度是无穷大。

    即便是那天比赛的冠军队，在做出这题时也欢呼了起来，可见它有多烦人。

    C. Palindromic Primes Category in Jeopardy

    问形如这样的问题：“小于 2³¹ 的 24 进制的回文素数有几个？” 提问的进制数包括 2 到 36 进制。看似有点难，但是我们队的打表王和素数王，各大 OJ 的风云人物， TRY 同学打表秒杀了此题。

    D. Pebbles

    一个 15 × 15 的矩阵，每格上都有一个大于 0 的得分；要求选取一些格子，使总得分最大；要求选取的任何两个格子都不能相邻。看上去应该是典型的 DP，状态数组的下标就是一行的各种选法，有 2¹⁵ 个状态；对每一行，枚举该行和上一行有所有选法，如果有不冲突的，则可以更新状态值。但是我们一开始想，每一行的状态有 2¹⁵ 个，那总的时间复杂度就是 O(15 × 2³⁰)，是不行的。可是后来恍然大悟，一行的选法不是 2¹⁵ 种，因为 0 ~ 2¹⁵ 之间二进制没有相邻的 1 的数只有 1000 多个，所以总的时间复杂度一下子就降低了，于是做出了此题。

    E. Rubik's Cube

    比较复杂的模拟题，当场很少有人碰，我们也不例外。可是我们学校的一支新队员队伍却做出了这道题，精神可嘉，令众人十分佩服。

    G. Frogger

     一个 30 × 30 的矩阵，有一个起点，若干个终点，走到任意一个终点就算到达目标；每一步可以上、下、左、右走，或者原地不动；有些格子是墙，不能走上去；有些墙是固定的，有些墙则是不断地横向循环移动的（移动到最左边则回到最右边）；要求算出从起点到终点的最短时间。

   由于墙是不断循环移动的，所以整个地图是周期性变化的，循环的周期长度就是地图的宽度。因此需要保存 30 张不同的地图， BFS 的每一步都走相应的地图即可。另外，比赛当时我们没把题目读懂，原来题目里说的是只有走到指定的一些格子上才耗费时间。所以我们当时没搞懂 SAMPLE OUTPUT，没来得及做出这题，赛后才做出。

    J. Cover Up

    我一开始就分配到读这道题，之后就一直在想它（除了当中被队友打岔，帮他们出点主意，或者自己分心想了想别的题目等等）。我全场比赛就做了这一道题，我的两个队友也很信任我，没有来过问。到第 4 小时左右的时候终于想出来了，这是我们队做出的最后一道题。

    说的是在一次抽奖活动中，中奖号码是 7 位数；每位数上都有 1 ~ 10 个不同的数供抽奖者选择；抽奖者在各位上随便选一个数，如果全选对了就中奖了；如果全选错了就淘汰；如果只选对了一部分，则选错的部分可以重选（当然，重选的时候，原来选错的数就排除掉了）；如此不断循环，直到全选对或者淘汰为止。问中奖率是多少？

    我一开始就觉得是 DP，可是 7 位数，每位上可选的数有 1 ~ 10 个，则状态有 10⁷ 种，太多了。后来我才想到，和 D 题一样，有很多状态是没有必要的。比如有 3 位上的可选数分别有 1、 2、 3 个，和 3 位分别有 3、 2、 1 个是等价的。所以状态数其实就是各位都递增的 7 位数的个数，我记得当时算出来大概只有 50,000 多个。于是就好解啦，状态转移就是一个不算难的概率计算，枚举各位选对还是选错的所有情况嘛。不久之后便提交通过了。

    K. Bridge Marble Rings

图 1

    如图 1 所示，有两个环，其中各有 13 个球，总共有 13 个黄的和 13 个灰的。中间有一个小环连接，小环可以旋转 180 度，使两个环上的各 3 个球互换。问最少把小环旋转几次，可以把所有的灰球移到左边（两个大环本身任意旋转是不需要代价的）。

    比赛时我最先读的就是这道题（因为我喜欢最先读最后一题），第一感觉就是双向 BFS，因为目标状态是唯一的嘛。可是乍一看状态好像太多了，当时就没敢多想，放在一边了。反正就算当时会做，比赛时间也来不及。今天我回过头又想了想，终于把它做了出来。

    双向 BFS 的思路是没错的。首先， SAMPLE OUTPUT 提示了我，如果两个环全都是一黄一灰间隔排列的，则答案是 6。我想，这组 CASE 应该是离目标很远的吧，怎么只要 6 步！难道所有的解都这么小？当我编好代码后试验了一下，果然如此，一般情况下都是 4、 5 步就搜到了。

    虽然我的双向 BFS 代码计算少数几组数据不慢，差不多半秒就能搜出一个，但是这道题目的输入数据量比较大，好像有上百组。所以我还需要一些优化。

    两个环总的排列好像有很多，有 26C13 ≈ 10⁷ 种，但是实际上没那么多，因为一个环的 13 种旋转都是一样的。所以总的排列数应该是 26C13 / (13 × 13) ≈ 60,000 种。我在程序里是这样处理的，用 13 位二进程表示一个环，我把每种环都循环移位 13 次，找出其中最小的一个来代表它，这个预处理起来是不需要多少时间的。既然状态这么少，是不是可以索性在预处理的时候，把所有可能的状态的解都算出来？不是的，因为扩展状态的时候还是要把两个环各转 13 次，需要 O(13 × 13) 的时间，这样总的复杂度就又变回 O(10⁷) 了；再加上这道题的内存有限制，不能开数组保存解，只能用 map，那么常数级的复杂度也会很大，全部预处理就会超时了。

    但是后来我想到，每次双向 BFS 的反向搜索那部分，其实都是重复的。我干嘛不先反向搜索 3 步，把这些状态保存好，然后每次只要搜索正向的 2、 3 步就好了。依此修改了代码之后，立即变得飞快了。
 
    其它的都是水题，就不说了。

    总地来说，这两场比赛嘛，让我们都做出 6 题了，肯定是难度不大。其实每年的暑期练习赛都是这样，看似做出的题挺多，其实真正到了地区赛，我们还是只能做出 1 题。所以这种比赛的成绩并不重要，重要的还是抓紧时间多训练训练吧。

    最近碰到了一道关于汉密尔顿回路的题目，又学到了一点东西。以前只知道求汉密尔顿回路是 NP 问题，是很难求的。但是现在我知道了汉密尔顿回路的存在有许多充分条件，即当图满足某些特定性质的时候，汉密尔顿回路一定存在，而且可以根据一些算法构造出来。

    PKU 2438 就是关于汉密尔顿回路最常见的一个充分条件，Dirac 定理：设一个无向图中有 N 个节点，若所有节点的度数都大于等于 N/2，则汉密尔顿回路一定存在。注意，“N/2” 中的除法不是整除，而是实数除法。如果 N 是偶数，当然没有歧义；如果 N 是奇数，则该条件中的 “N/2” 等价于 “⌈N/2⌉”。

    证明起来不难。首先可以证明图一定是连通的。设 d(v) 表示节点 v 的度数。对于任意两个节点 u、 v，若它们不相邻，则可能和它们相邻的节点共有 N - 2 个，而 d(u) + d(v) ≥ N/2 + N/2 ≥ N，那么根据鸽巢原理，肯定存在一个节点与 u 和 v 都相邻。即证，任何两个节点之间都是连通的。

    接下来，证明汉密尔顿回路存在的过程其实就是构造这条回路的过程，分成以下几个步骤：

1. 任意找两个相邻的节点 S 和 T，在它们基础上扩展出一条尽量长的没有重复节点的路径。也就是说，如果 S 与节点 v 相邻，而且 v 不在路径 S → T 上，则可以把该路径变成 v → S → T，然后 v 成为新的 S。从 S 和 T 分别向两头扩展，直到无法扩为止，即所有与 S 或 T 相邻的节点都在路径 S → T 上。

2. 若 S 与 T 相邻，则路径 S → T 形成了一个回路。

3. 若 S 与 T 不相邻，可以构造出一个回路。设路径 S → T 上有 k + 2 个节点，依次为 S、 v1、 v2…… vk  和 T。可以证明存在节点 vi， i ∈ [1, k)，满足 vi 与 T 相邻，且 vi+1 与 S 相邻。证明方法也是根据鸽巢原理，既然与 S 和 T 相邻的点都在该路径上，它们分布的范围只有 v1 ∼ vk 这 k 个点， k ≤ N - 2，而 d(S) + d(T) ≥ N，那么可以想像，肯定存在一个与 S 相邻的点 vi 和一个与 T 相邻的点 vj， 满足 j < i。那么上面的命题也就显然成立了。 找到了满足条件的节点 vi 以后，就可以把原路径变成 S → vi+1 → T → vi → S，即形成了一个回路。

4. 现在我们有了一个没有重复节点的回路。如果它的长度为 N，则汉密尔顿回路就找到了。 如果回路的长度小于 N，由于整个图是连通的，所以在该回路上，一定存在一点与回路以外的点相邻。那么从该点处把回路断开，就变回了一条路径。再按照步骤 1 的方法尽量扩展路径，则一定有新的节点被加进来。接着回到步骤 2。

    在整个构造过程中，如果说每次到步骤 4 算是一轮的话，那么由于每一轮当中，至少有一个节点被加入到路径 S → T 中来，所以总的轮数肯定不超过 N 轮。实际上，不难看出该算法的复杂度就是 O(N²)，因为总共扩展了 N 步路径，每步扩展最多枚举所有的节点。

    虽然这次表演不是很完美，但是在排练的这一个多月里，我的身体真的健康了不少。我也要感谢社长同学安排我做连续后旋，这么看得起我。我之后就一直在练转啊转，都快练成芭蕾舞演员了。可惜表演时还是失误频频，我擅长的旋风踢居然摔倒了，可能是转晕了吧。不过总之大家玩得很开心。

    鸽巢原理人人都有耳闻，十只鸽子飞进九个巢，必定有一个巢里不少于两只鸽子。但是真正要用的时候，它却总是来得悄无声息。就像电影《The Blues Brothers》里面的牧师说的：“The day of the Lord cometh is as a thief in the night”。

    ZJU 2955 乍一看是再典型不过的动态规划问题：给出 N （N < 100）个 (0, 100) 范围内的整数，问最少从中取出几个数，可以使它们相加正好等于一个指定的整数 S（每个数可以取的次数不限）。

    有一点 ACM 经验的同学肯定一看就知道这是一个 O(S × N) 的动态规划。可是问题是，这道题目里 S 的范围是 [1, 10⁹]。要解决这个问题，首先需要用鸽巢原理来证明下面这个定理：

    设可选的 N 个数从小到大依次为 a₍₁₎、 a₍₂₎ … a_(N)，则在最优的取法中，小于 a_(N) 的数不会多于 a_(N) 个。

    可以用反证法来证明。假设在最优的取法中，有 M 个小于 a_(N) 的数（M > a_(N)）。让我们把这 M 个数随便排列起来，记为 b₁、 b₂ … b_M。再设 S_i = b₁ + b₂ … + b_i （1 ≤ i ≤ M）。

    由于一个数除以 a_(N) 的余数只有 a_(N) 种可能性，即 0 到 a_(N) - 1，又因为 M > a_(N)，所以一定存在一对 S_i 与 S_j （1 ≤ i < j ≤ M）满足 S_i mod a_(N) = S_j mod a_(N)。也就是说，S_j - S_i 是 a_(N) 的倍数，也就是说，b_{i + 1} + b_{i +2} … + b_j 是 a_(N) 的倍数。然而，根据之前的假设，b₁ … b_M 都是小于 a_(N) 的。因此，如果把 b_{i + 1} + b_{i +2} … + b_j 这一块全部用 a_(N) 来填补，则可以用更少的数。这样一来，假设中的取法就不是最优取法了。反证完毕。□

    有了上面的定理，问题就好解决了。不多于 a_(N) 个小于 a_(N) 的数，加起来的和不会超过 a_(N)² ，即不超过 10,000。S 在这个范围内的最优解是可以用动态规划全部求出来的，花 O(10⁶) 的时间。如果 S > a_(N)² 的话，只要枚举所有的 S’ ∈ [1, a_(N)²]，然后 S - S’ 的部份全部用 a_(N) 来填充，即可找到最优解。

    这道题目的大意是这样的：

• 有 M 个猪圈（M ≤ 1000），每个猪圈里初始时有若干头猪。
• 一开始所有猪圈都是关闭的。
• 依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，从中买若干头猪。
• 每个顾客分别都有他能够买的数量的上限。
• 每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。

    问总共最多能卖出多少头猪。

    举个例子来说。有 3 个猪圈，初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客，第一个打开 1 号 和 2 号猪圈，最多买 2 头；第二个打开 1 号 和 3 号猪圈，最多买 3 头；第三个打开 2 号猪圈，最多买 6 头。那么，最好的可能性之一就是第一个顾客从 1 号圈买 2 头，然后把 1 号圈剩下的 1 头放到 2 号圈；第二个顾客从 3 号圈买 3 头；第三个顾客从 2 号圈买 2 头。总共卖出 2 + 3 + 2 = 7 头。□

    不难想像，这个问题的网络模型可以很直观地构造出来。就拿上面的例子来说，可以构造出图 1 所示的模型（图中凡是没有标数字的边，容量都是 +∞）：

• 三个顾客，就有三轮交易，每一轮分别都有 3 个猪圈和 1 个顾客的节点。
• 从源点到第一轮的各个猪圈各有一条边，容量就是各个猪圈里的猪的初始数量。
• 从各个顾客到汇点各有一条边，容量就是各个顾客能买的数量上限。
• 在某一轮中，从该顾客打开的所有猪圈都有一条边连向该顾客，容量都是 +∞。
• 最后一轮除外，从每一轮的 i 号猪圈都有一条边连向下一轮的 i 号猪圈，容量都是 +∞，表示这一轮剩下的猪可以留到下一轮。
• 最后一轮除外，从每一轮被打开的所有猪圈，到下一轮的同样这些猪圈，两两之间都要连一条边，表示它们之间可以任意流通。

    不难想像，这个网络模型的最大流量就是最多能卖出的数量。图中最多有 2 + N + M × N ≈ 100,000 个节点。□

    这个模型虽然很直观，但是节点数太多了，计算速度肯定会很慢。其实不用再想别的算法，就让我们继续上面的例子，用合并的方法来简化这个网络模型。

    首先，最后一轮中没有打开的猪圈就可以从图中删掉了，也就是图 2 中红色的部分，显然它们对整个网络的流量没有任何影响。


    接着，看图 2 中蓝色的部分。根据我总结出的以下几个规律，可以把这 4 个点合并成一个：

    规律 1. 如果几个节点的流量的来源完全相同，则可以把它们合并成一个。

    规律 2. 如果几个节点的流量的去向完全相同，则可以把它们合并成一个。

    规律 3. 如果从点 u 到点 v 有一条流容量为 +∞ 的边，并且点 v 除了点 u 以外没有别的流量来源，则可以把这两个节点合并成一个。

    根据规律 1，可以把蓝色部分右边的 1、 2 号节点合并成一个；根据规律 2，可以把蓝色部分左边的 1、 2 号节点合并成一个；最后，根据规律 3，可以把蓝色部分的左边和右边（已经分别合并成了一个节点）合并成一个节点。于是，图 2 被简化成了图 3 的样子。也就是说，最后一轮除外，每一轮被打开的猪圈和下一轮的同样这些猪圈都可以被合并成一个点。


    接着，根据规律 3，图 3 中的蓝色节点、2 号猪圈和 1 号顾客这三点可以合并成一个；图 3 中的两个 3 号猪圈和 2 号顾客也可以合并成一个点。当然，如果两点之间有多条同向的边，则这些边可以合并成一条，容量相加，这个道理很简单，就不用我多说了。最终，上例中的网络模型被简化成了图 4 的样子。□



    让我们从图 4 中重新总结一下构造这个网络模型的规则：

• 每个顾客分别用一个节点来表示。
• 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
• 对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为 +∞。
• 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

    拿我们前面一直在讲的例子来说：1 号猪圈的第一个顾客是 1 号顾客，所以从源点到 1 号顾客有一条容量为 3 的边；1 号猪圈的第二个顾客是 2 号顾客，因此从 1 号顾客到 2 号顾客有一条容量为 +∞ 的边；2 号猪圈的第一个顾客也是 1 号顾客，所以从源点到 1 号顾客有一条容量为 1 的边，和之前已有的一条边合并起来，容量变成 4；2 号猪圈的第二个顾客是 3 号顾客，因此从 1 号顾客到 3 号顾客有一条容量为 +∞ 的边；3 号猪圈的第一个顾客是 2 号顾客，所以从源点到 2 号顾客有一条容量为 10 的边。□

    新的网络模型中最多只有 2 + N = 102 个节点，计算速度就可以相当快了。可以这样理解这个新的网络模型：对于某一个顾客，如果他打开了猪圈 h，则在他走后，他打开的所有猪圈里剩下的猪都有可能被换到 h 中，因而这些猪都有可能被 h 的下一个顾客买走。所以对于一个顾客打开的所有猪圈，从该顾客到各猪圈的下一个顾客，都要连一条容量为 +∞ 的边。

    在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最直观，或者说最“硬来”的模型，然后再用合并节点和边的方法来简直化这个模型。经过简化以后，好的构图思路自然就会涌现出来了。这是解决网络流问题的一个好方法。