2.9 图论模型与算法
本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第11章。
习题11-1 网页跳跃（Page Hopping, ACM/ICPC World Finals 2000, UVa821）
最近的研究表明，互联网上任何一个网页在平均情况下最多只需要点击19次就能到达任意一个其他网页。如果把网页看成一个有向图中结点，则该图中任意两点间最短距离的平均值为19。
输入一个n（1≤n≤100）个点的有向图，假定任意两点之间都相互到达，求任意两点间最短距离的平均值。输入保证没有自环。
【分析】
模型就是带权有向图，权值是两点之间的距离，则使用Floyd算法就可以计算出任意两点之间的最短距离，最后求平均值。关于Floyd算法，请参考《算法竞赛入门经典（第2版）》中的11.2.5节。
习题11-2 奶酪里的老鼠（Say Cheese, ACM/ICPC World Finals 2001, UVa1001）
无限大的奶酪里有n（0≤n≤100）个球形的洞。你的任务是帮助小老鼠A用最短的时间到达小老鼠O所在位置。奶酪里的移动速度为10秒一个单位，但是在洞里可以瞬间移动。洞和洞可以相交。输入n个球的位置和半径，以及A和O的坐标，求最短时间。
【分析】
把起点A和目标点O都看作半径为0的球，则共有n+2个球。把每个球的球心看作结点，则两个球(p1,r1)和(p2,r2)所对应的结点之间的距离为d=|p1-p2|-r1 – r2，如果d< 0，说明两个球相交，可以认为d=0。求出所有顶点之间的距离之后，任意两个球对应的结点之间都有一个距离为d的无向边。使用Floyd算法即可求出A和O之间的最短距离。
习题11-3 因特网带宽（Internet Bandwidth, ACM/ICPC World Finals 2000, UVa820）
在因特网上，计算机是相互连通的，两台计算机之间可能有多条信息连通路径。流通容量是指两台计算机之间单位时间内信息的最大流量。不同路径上的信息流通是可以同时进行的。例如，图2.72中有4台计算机，总共5条路径，每条路径都标有流通容量。从计算机1到计算机4的流通总容量是25，因为路径1-2-4的容量为10，路径1-3-4的容量为10，路径1-2-3-4的容量为5。
图2.72
请编写一个程序，在给出所有计算机之间的路径和路径容量后求出两个给定结点之间的流通总容量（假设路径是双向的，且两方向流动的容量相同）。
【分析】
把每个计算机看作一个结点，图2.72中每条路径对应有向图中两条边，容量都是路径的容量。之后应用Dinic算法求出给定结点之间的最大流即可。关于Dinic算法，请参考《算法竞赛入门经典—训练指南》中的5.6.1节。
习题11-4 电视网络（Cable TV Network, ACM/ICPC SEERC 2004, UVa1660）
给定一个n（n≤50）个点的无向图，求它的点连通度，即最少删除多少个点，使得图不连通。如图2.73（a）所示的点连通度为3，图2.73（b）所示的连通度为0，图2.73（c）所示的点连通度为2（删除1和2或者1和3）。
图2.73
【分析】
注意只要使得任意两个点不连通即可。将每个点i拆成两个点i和i+n。建立一条有向边i→i+n，容量为1。对于原图中的边(i,j)，建立两条边(i+n→j), (j+n→i)，容量为INF。两两遍历点对(u,v)，令u+n为源点s，v为汇点t。则要使u和v不连通所需删除的点对应于s到t之间由容量为1的边组成的割。这个点集大小的最小值，等于s→t最小割的容量。在所有的最小割容量中取最小值即是所求的点连通度。关于最小割的求法，请参考《算法竞赛入门经典（第2版）》中的11.4.3节。完整程序如下：
习题11-5 方程（Equation, ACM/ICPC NEERC 2007, UVa1661）
输入一个后缀表达式f(x)，解方程f(x)=0。表达式包含四则运算符，且x最多出现一次。保证不会出现除以常数0的情况，即至少存在一个x，使得f(x)不会除0。所谓后缀表达式，是指把运算符写在运算数的后面。例如，(4x+2)/2的后缀表达式为4 x* 2+2 /。样例输入与输出如表2.3所示。
表2.3
【分析】
第一步首先要将输入的表达式解析成表达式树，解析的过程实际上是递归的，输入运算符op的位置end，得到op对应的表达式树，同时将end更新到解析出的表达式的左边位置。
解析完表达式之后，求解的过程依然是递归的，给定一个表达式树的根结点p，以及这个表达式的值v。因为题目条件中x只存在于一个结点，要么属于p的左子树，要么就是右子树。而x所在的子树的值就是未知的。首先根据p对应的运算符以及v求出x所在的子树的值（解一个一元方程），然后往下递归。发现任何无解或者有无数多个解时终止递归，主要是牵涉乘法和除法时有各种的特殊情况需要处理，详情请参见代码。
同时需要注意的是，求解的过程中的数值类型需要使用自定义的有理数类型，并且有理数的分子分母都需要使用64位的long long来保存，否则可能会溢出。
习题11-6 括号（Brackets Removal, NEERC 2005, UVa1662）
给一个长度为n的表达式，包含字母、二元四则运算符和括号，要求去掉尽量多的括号。去括号规则如下：若A和B是表达式，则A+(B)可变为A+B，A-(B)可变为A-B'，其中B'为B把顶层“+”与“-”互换得到；若A和B为乘法项（term），则A*(B)变为A*B，A/(B)变为A/B'，其中B'为B把顶层“*”与“/”互换得到。本题只能用结合律，不能用交换律和分配律。
例如，((a-b)-(c-d)-(z*z*g/f)/(p*(t))*((y-u)))去掉括号以后为a-b-c+d-z*z*g/f/p/t*(y-u)。
【分析】
首先使用《算法竞赛入门经典》中的11.1.2节中介绍的递归下降法对表达式进行解析，建立表达式树。树的结点包含：
（1）当前的运算符或字母。
（2）是否包含在括号内。
（3）运算符的优先级。
乘除的优先级比加减高。解析的过程中，如果发现一个序列左右两端有括号，则需要设置对应结点的标志位。
解析完成之后，对整棵树进行去括号的处理，处理顺序是从根结点递归往下：
（1）对于左结点，如果其优先级大于或等于当前结点，直接去掉其括号然后对其进行递归去括号处理。
（2）对于右结点，如果其优先级高于当前结点，直接去掉其括号即可。
（3）如果右结点优先级等于当前结点，并且发现需要当前结点为“-”或者“/”进行运算符的求反，如-(b-c)这样或者/(b/c)这样的表达式，那么就需要进行运算符取反处理，递归往下每次遇到左结点如果优先级等于上级结点，就取反。
（4）右结点取反之后，再对其进行去括号处理。
习题11-7 电梯换乘（Lift Hopping, UVa 10801）
在一个假想的大楼里，有编号为0～99的100层楼，还有n（n≤5）座电梯。你的任务是从第0楼到达第k楼。每个电梯都有一个运行速度，表示到达一个相邻楼层需要的时间（单位：秒）。由于每个电梯不一定每层都停靠，有时需要从一个电梯换到另一个电梯。换电梯时间总共1分钟，但前提是两座电梯都能停靠在换乘楼层。大楼里没有其他人和你抢电梯，但你不能使用楼梯（这是一个假想的大楼，你无须关心它是否真实存在）。
例如，有3个电梯，速度分别为10、50、100，电梯1停靠0、10、30、40楼，电梯2停靠0、20、30楼，电梯3停靠第0、20、50楼，则从0楼到50楼至少需要3920秒，方法是坐电梯1到达30楼（300秒），坐电梯2到达20楼（500秒+换乘60秒），再坐电梯3到达50楼（3000秒+换乘60秒），一共300+500+60+3000+60=3920秒。
【分析】
将每一层楼内每个电梯在该层的出口看作一个顶点，对于电梯x来说，假如它在第i层停靠，把x在i层的出口看作一个顶点记为x*100+i。对于x的下一个停靠层j来说，x* 100+j和x*100+i可以连一条边，权值就是这个电梯从i到j层所需要的运行时间。而对于同样在i层停靠的每个电梯y来说，x*100+i到y*100+i也连一条边，权值为60（同层换乘）。
图建好之后，遍历所有的形为x*100的点u和y*100+k的v，使用dijkstra算法求出所有u、v间最短距离的最小值即为所求结果。完整程序（C++11）如下：
习题11-8 净化器（Purifying Machine, ACM/ICPC Beijing 2005, UVa1663）
给m个长度为n的模板串。每个模板串包含字符0、1和最多一个星号“*”，其中星号可以匹配0或1。倒如，模板01*可以匹配010和011两个串，而模板集合{*01, 100, 011}可以匹配串{001, 101, 100, 011}。
你的任务是改写这个模板集合，使得模板的个数最少。例如，上述模板集合{*01, 100, 011}可以改写成{0*1, 10*}，匹配到的字符串集合仍然是{001, 101, 100, 011}。n≤10，m≤1000。
【分析】
拿到一个输入串之后，首先展开成可以匹配的串集合S，S中的元素用对应的整数值来表示。例如{*01, 100, 011}→{101, 001, 100, 011}→{5, 1, 4, 3}。
两两判断这个S中的点s1, s2，如果二者的二进制只有一位不同，在s1和s2之间连一条边，对应一个带“*”的模板串，其中“*”的位置就是s1和s2不同的那一位。而s1和s2中1的个数的奇偶性必然不同。可以按照这个奇偶性将所有点分成两类，就形成一个二分图。而这个二分图的每一个匹配都对应于一个带“*”的模板集合。求此二分图的最大匹配，假设其中有n条边，则所求的模板集合的最小值就是|S|-n。
完整程序如下：
习题11-9 机器人警卫（Sentry Robots, ACM/ICPC SWERC 2012, UVa12549）
在一个Y行X列（1≤Y, X≤100）的网格里有空地（.）、重要位置（*）和障碍物（#），如图2.74所示。用最少的机器人看守所有重要位置。每个机器人要放在一个格子里，面朝上、下、左、右4个方向之一。机器人会发出激光，一直射到障碍物为止，沿途都是看守范围。机器人不会阻挡射线，但不同的机器人不能放在同一个格子。
图2.74
【分析】
需要注意的是，机器人放到重要位置上，看守这个重要位置。
考虑没有障碍物的简单情况，实际上就是《算法竞赛入门经典—训练指南》的第5.5.4节中的例题27（UVa11419）。建模过程如下：把每一行看作一个X结点，每一列看作一个Y结点，每个重要位置看作一条边连接相应的行结点和列结点。同一行或列只需要放置一个机器人，就可以看守所在同一行或同一列上的所有重要位置。这样就要求选择一组结点，使得每个所有重要位置对应的边都至少有1个结点被覆盖。这样就转换成为求二分图的最小覆盖，可以证明最小覆盖等于最大匹配数。
这样，问题的关键就在于能否把带有障碍物的模型转换成为不带障碍物的模型。首先按照行进行转换：从上到下，从左到右遍历每个点，遇到障碍物时，就将障碍物以及所有右边的点（包括障碍物和重要位置）向下平移一行，这样将左边的点和右边的点分割成上下两行。如图2.75所示为每个点的坐标以及做了上述水平转换后的坐标。这样，被障碍物隔开的两边的点就可以分成独立的两行，分别由单独机器人进行看守。同理，按行进行转换之后，继续按照列进行类似的转换。
图2.75
转换完成之后，点水平和垂直坐标的最大值分别是X+2*W、Y+2*W，这也是建成的二分图的X和Y点数的最大值，而重要位置的个数（也就是说二分图的边数）依然是P。完整程序（C++11）如下：
习题11-11 占领新区域（Conquer a New Region, ACM/ICPC Changchun 2012, UVa1664）
假设n（n≤200000）个城市形成一棵树，每条边有权值C(i,j)。任意两个点的容量S(i,j)定义为i与j唯一通路上容量的最小值。找一个点（它将成为中心城市），使得它到其他所有点的容量之和最大。
【分析】
因为是一棵树，任意一条边都可以将整个图分成两棵树，所求的中心点一定是在其中一棵树中，由此想到一开始可以从每个点开始求中心点，然后不断合并。
参考Kruskal算法的思路，首先初始化并查集，一开始每个集合的代表元素都是中心点，维护每个点集的元素个数Cnt[i]以及中心点到其他点的容量之和WS[i]，其中i是这个元素的代表元，一开始i肯定是所在点集的中心城市，且WS[i]=0。
把所有边按权值从大到小排序，依次遍历每条边e，使用e将已有两个点集连起来。记这两个点集为A、B，中心点分别是a、b。因为已经排序，e一定是连接来自两个点集的边中权值最小的，而且分别来自A和B的任意两点之间的唯一通路一定经过e，所以通路的容量一定为e的权值。
然后考虑A和B合并之后的点集，如果要把b作为其中心点，产生的新的点集的容量就是Wb=WS[b]+Cnt[a]*w，其中w是e的权值。而b到A中每个点的容量都是w。反过来把a作为中心点产生的新点集容量是Wa=WS[a]+Cnt[b]*w。不妨设Wa>Wb，把B合并到A中，a就是新的点集的符合要求的中心点。所有边遍历完成之后，合并完成的集合的代表元就是所求的中心点，算法的时间复杂度为O(N)。完整程序如下：
本题的严格证明留给读者思考。
习题11-12 岛屿（Islands, ACM/ICPC CERC 2009, UVa1665）
输入一个n*m（1≤n,m≤1000）矩阵，每个格子里都有一个[1,109]正整数。再输入T（1≤T≤105）个整数ti（0≤t1≤t2≤…≤tT≤109)，对于每个ti，输出大于ti的正整数组成多少个四连块。如图2.76所示，大于1的正整数组成两块，大于2的组成3块。
图2.76
评论：这个题目虽然和图论没什么关系，但是可以用到本章介绍的某个数据结构。
【分析】
因为牵涉集合的查询合并，首先可以使用并查集来表示连续的格子组成的集合。最简单的做法就是从大到小遍历所有的t，每次查找对应的格子，但是粗略估计时间复杂度至少是T*n*m=1011，必然会超时。这样可以将所有的格子按照值从大到小排序，然后每次只查找对应的格子，并且复用上次遍历的结果。
具体来说，可以用一个结构P{x,y,v}表示位置是[x,y]且值为v的数字。然后按照v从大到小对所有的P排序，初始每个P属于一个独立的集合（块）。之后按照从大到小的顺序，遍历ti。记ans为开始遍历时符合条件的集合的个数。i=T则ans=0，否则ans初始就是ti+1对应的结果。从大到小依次扫描ti+1>v>ti的所有点p。每遍历到一个p，ans加1，然后依次查看p在矩阵中的4个邻居pn，如果pn.v > ti，且pn和p不在同一个集合，则将pn和p所在的集合合并，ans减1。扫描完符合条件的P之后ans就是符合v> ti的集合个数。
虽然是两层循环，但是内层循序实际上是不重复地遍历所有格子，总的循环次数是nm。时间复杂度为O(nm*α(mn)+T)。这里α表示并查集查找过程的时间复杂度，基本上可以认为是常量，不大于4，具体的分析请参考《算法导论》一书的21.4节。完整程序（C++11）如下：
习题11-14 乱糟糟的网络（Network Mess, ACM/ICPC Tokyo 2005, UVa1667）
有一棵n（n≤50）个叶子的无权树。输入两两叶子的距离，恢复出这棵树并输出每个非叶子结点的度数。
【分析】
面对这种无根的树型结构，一般一开始就任意取一个叶子结点u作为根。记f(i,j)为i和j两个叶子之间的距离。
递归处理：输入以u为根的子树的所有叶子结点以及u到所有叶子的距离。枚举它的任意两个叶子i、j，如图2.77所示。
（1）f(u,i)+f(u,j) > f(i,j)，说明i和j是在u为根的树的同一个子树。
（2）f(u,i)+f(u,j)=f(i,j)，说明i和j不在同一棵子树中。
图2.77
然后用并查集对所有的u的叶子进行分组，分成不同的子树，同时创建对应的子树根。在往下递归之前，应该将所有的叶子结点到根结点的距离都减一。
在这个过程中，对于f(u,i)=1的情况，说明i就是u的直接叶子结点，不需要往下递归，但是需要构造一个相应的叶子结点方便进行统计。通过上述逻辑，就可以找出哪些叶子在同一棵子树中，以及u有多少棵子树。完整程序（C++11）如下：
习题11-16 交换房子（Holiday's Accomodation, ACM/ICPC Chengdu 2011, UVa1669）
有一棵n（2≤n≤105）个结点的树，每个结点住着一个人。这些人想交换房子（即每个人都要去另外一个人的房子，并且不同人不能去同一个房子）。要求安排每个人的行程，使得所有人旅行的路程长度之和最大。
【分析】
因为是一棵树，安排好的符合条件的行程中，假如有两对结点（u1,u2）和（v1,v2）。u1要到v1，u2要到v2，而且这两条路径不相交。那么在两条路径上分别选择点p1和p2，则重新做如下安排：u1→p1→p2→v2，u2→p2→p2→v2，其中记p1→p2的路径长度为pl，显然这样安排的路径相交而且长度之和比之前的长度长2*pl。由此可以证明，任意两个行程的路径必定相交。
首先任选一个结点作为根，构造整棵树，同时对每个结点u记录以u为根结点的子树的结点个数Du。然后对于每个长度为w的边e，假设这条边将树分成A、B两颗子树，根据上述结论可以得出经过这条边的路径的条数就是me=2*min{DA, n-DA}。对所有边求
即可得所求结果。至于如何求每颗子树的结点个数，可以使用《算法竞赛入门经典（第2版）》中的9.4.2节，《树的重心》部分的树形DP过程。
习题11-17 王国的道路图（Kingdom Roadmap, ACM/ICPC NEERC 2011, UVa1670）
输入一个n（n≤100000）个结点的树，添加尽量少的边，使得任意删除一条边之后图仍然连通。如图2.78所示，最优方案用虚线表示。
【分析】
图2.78
要满足所求的条件，保证结果的图中没有桥即可，可将每个叶子都和其他叶子相连。任意选择一个度数为1的非叶子结点作为树根，然后依次对每颗子树进行递归操作。
对于每颗子树：把悬在桥上的叶子依次配对连起来，但是要保证留下至少一个传回给父结点，以便最终和根结点配对。对于根结点，如果剩下两个叶子，就把它们连起来，如果剩一个，就在这个叶子和根结点之间连一条边。
证明留给读者思考。完整程序（C++11）如下：
习题11-20 租车（Rent a Car, UVa12433）
如果你想经营一家租车公司。接下来的N天中已经有了一些订单，其中第i天需要rj辆车（0≤rj≤100）。初始时，你的仓库是空的，需要从C家汽车公司买车，其中第i家公司里有ci辆车，单价是pi（1≤ci,pi≤100）。当一辆车被归还给租车公司之后，你必须把它送去保养之后才能再次租出去。一共有R家服务中心，其中第i家保养一次需要di天，每辆车的费用为si（1≤di,si≤100）。这些服务中心都很大，可以接受任意多辆车同时保养。你的仓库很大，可以容纳任意多辆车。你的任务是用最小的费用满足所有订单。1≤N,C, R≤50。
例如，N=3，C=2，R=1，r={10,20,30}，c1=40，p1=90，c2=15，p2=100。d1=1，s1=5，最优方案是这样的：先买50辆车，其中在公司1买40辆，公司2买10辆，费用为90*40+100*10=4600。第一天白天租出去10辆车，晚上收回之后送到服务中心保养一天，费用为5*10=50，第3天白天可以再次出租。第2天出租20辆车，第3天把剩下的20辆车和保养后的10辆车一起出租。总费用为4600+50=4650。
【分析】
建立源点S和汇点T。对于第i天，建立两个结点Gi和Qi，分别表示当天的待租车库，以及待保养车库（存放当天返回的待保养车），从Gi到T建立一条边，容量为当天的市场需求ri，费用为0，表示当天需要租出ri辆车。从S到Qi建一条边，容量为ri，费用为0，代表从市场归还的ri辆车。从Gi-1到Gi建立一条边，容量为INF，费用为0。表示汽车可以在租车公司存着不租出去。而对于每一个汽车公司，从S到G0建立一条容量为c，费用为p的边，表示第一天可以买到的车。
对于每个服务中心，因为从第i天市场返回来的车要在第i+1天送修并且在第i+d+1天才送回租车公司供后续出租，所以从Qi到Gi+d+1，建立一条边（前提是i+d+1 < N），容量为INF，费用为保养费用s。图2.79展示了题目描述案例对应的图的结构。
图2.79
这样S→T的最小费用就是所求的最小费用，直接用MCMF求最小费用最大流即可，求出最小费用之后，看每条到T的边容量是否是最大值，也就是说满足了当天的市场需求。如果全部满足，直接输出最小费用，否则说明不满足，输出impossible。
这个题目的难点在于：如何表示从服务中心保养返回的车，实际上这些流量是在每一天“返回”了，那么就从源点到每一天的待保养车库建一条边即可，表示流量用完之后又“回来”了。另外对于服务中心及汽车公司，虽然直观概念上是一个点，但是本质上只是有费用流量的路径而已，不用在建模时建立这个点，直接建边即可。
MCMF算法的实现可以参考《算法竞赛入门经典—训练指南》中的5.6.2节。费用要使用64位的long long来存储，以免溢出。