算法艺术与信息学竞赛习题部分提示(3)

所以不存在过这些点的环。在A没有能到达安全点之前，它所能到的点都不是安全点，

这些点必定构成一棵树。如果以A的出发点作为根R，那么要从根R的一棵子树上的某一点到达另一棵子树上的某一点，必须要经过根R（在完整的图中也是如此）。否则我们就可以得到一个过根R的环，与根R不是安全点矛盾。同理，对于根R的一个儿子Q，Q的一棵子树上的某一点到达另一棵子树上的某一点，必须要经过Q（在完整的图中也是如此）。……因此，B一定会在树中的X点上第一次出现，这个X是一定的。（当B的出发点在树上时，这个X就是他的出发点）。

在A没有到达安全点之前，他到树上的每一个点都只有一条路。他应当事先定好一个目标，朝着一个希望点走（我们把与安全点相邻的树上的点称为希望点）。如果要改变目标，他就只能走回头路，这样显然是不合算的。所以A无法根据B的走法来及时调整自己的策略。而B的目标也是相当明确的，就是朝着根的方向走，尽快地卡住要道。因为，随着树的深度的增加，分叉会越来越多，其中有希望点的几率也相应增大。

对于树上的某一个点P，如果X是P的一棵子树上的点、在P的另一棵子树上有希望点，那么若A能够比B早一轮到达P，A就一定能安全到达安全点。反之，如果对于所有这样的P，A都不能比B早到，那么A的所有通向安全点的道路都会被B堵死，A迟早会被B抓到。

这里R和X都在树上，所以R和X到树上的点的路线都是唯一的。所以，我们可以用宽度优先搜索来判断究竟是A能率先到达安全点还是B能抢先一步卡住咽喉要道。

我们首先要找出所有的安全点。我们从点1开始做宽度优先搜索。每出现一条横向边，就表示找到了一个环。找出这个环上的所有点，然后把它们都记为安全点。

接着，我们用宽度优先搜索分别计算每一回合后A、B两人可以到达的格子。我们先搜B的，再搜A的（这和题中两人走棋的顺序相反）。对于一个点，如果B已经到达过了，

算法艺术与信息学竞赛习题部分提示

那么A就不能再去了，否则就一定会被抓住。如果A能安全到达一个安全点，那么B就再也抓不到A了，程序就应该马上终止。当B能到达所有A能到达的格子后，那么A就无路可走了。这时所用的步数就是B抓到A所需要的步数。

我们要开一个布尔型数组，记录每个点是否为安全点。在宽度优先搜索中还需要开几个数组。

在解题的过程中，我们只用到了宽度优先搜索，所以算法的时间复杂度是O(n+m)，其中n是格子的个数，m是相邻的格子的对数。由于m 15000且n 3000，所以这个算法是非常理想的。程序的空间需求也不大，大约为300k。

2.5节习题

2.5.1 最公平路

从小到大枚举最小边，则最大边不减。每次用O(m)的时间判连通即可。

2.5.3 最小圈

初始时设置d[i,i]=无穷大，再套用floyd-warshall算法即可。

2.5.6 路的最小公倍数

那么一条路p的s(p)值中a的指数就是p上的权中a的最小指数， 单独考虑每个素数a，

即路的“瓶颈”。所有s(p)的最小公倍数就是所有路的瓶颈最大值。把“求和”操作改成“取最小值”操作，然后套用dijkstra即可。

2.5.7 货币兑换

这道题目的本质是判断加权有向图是否有正圈，套用bellman-ford算法即可。如果迭代n-1次以后标号仍然会改变，则有正圈。为了找到正圈，需要记录每个标号变化最后一次是由那个结点引起的。

2.5.8 速度限制

如果每条道路都有限速标志，那么此问题只是最普通的最短路径。基于此，我们尝试给每条道路标上限速标志。

如果上一条道路亦无标志，那么它们的速无标志路径的速度由上一条道路的速度决定；

度又由上两条道路的速度决定；如果上两条道路亦无标志，那么它们的速度又由上三条道路的速度决定……如此向前追溯，直至遇到有标志路径或者起点。所以逆向思维，我们从每一条有标志路径或者起点出发，在它们的后面接上所有单独的或者一串连续的无标志路径，使之成为一条有限速标志的新路。这样，此问题就转化为普通最短路径。当然，如何求出所有单独的或者一串连续的无标志路径可以用O(n3)的Floyd算法。

2.5.9 会议呼叫

首先，激活的边是不可能产生环的，所以形成了一棵树，而且只有一个分叉点。先从A，B，C出发调用SSSP，这一步是O(m+nlogn)的。然后枚举这个分叉点x，让d[A,x]+d[B,x]+d[C,x]尽量大。这一步是O(n)的。

2.5.11 开发计划

算法艺术与信息学竞赛习题部分提示

这道题目是“航天计划问题”的直接推广。

2.5.12 因特网宽带

这是个普通的最大流的模型。不同于一般书上此类算法之处在于，本题是无向图的关系，所以每条弧（两点之间的路径）是无向的，因此在具体计算过程中，每次找最短路进行增流，弧的实际方向是动态变化的，这就需要进行判断。判断的方法也很简单：设从第I个点对第J个点进行分析的，记流量为F，容量为C，那么如果F[i,j]<C[i,j]并且F[j,i] = 0，即不存在反向的流量，则可以正向扩展i->j；如果F[j,i] > 0 ，那么可以进行反向扩展。

2.5.13 出题者的烦恼

X结点是题目，Y结点是类别，如果题目a属于类别b则连边Xa->Yb，容量为1。对于每个Xa，连边s->Xa，容量为1。对于每个Yb，连边Yb->t，容量为第b类需要的试题数目。注意本题不是求最大流而是固定流量为给定数k的流，因此用增广路算法比较合适，每次流量增加1（因此ford-fulkerson算法是不适用的！），恰好为k时停止。

2.5.14 马戏团

本题是标准的最小路径覆盖问题。

2.5.15 锦标赛

X结点是还没有进行的比赛，Y结点是人，如果比赛a的双方是p和q，则连边Xa->Yp和Xa->Yq，容量都为1。对于每个比赛a，连边s->Xa，容量为1；对于每个人a，连边Ya->t，容量为...直观的说，这个容量是此人能取胜的最大场数。枚举冠军，则最好情况就是让他所有比赛都取得胜利，然后枚举第二名取胜的分数，就可以计算出每个人最多能够取胜的场数maxa，这就是刚才提到的容量。

2.5.17 方格取数

把方格黑白染色，相邻的格子连一条线。如果每个数并不是很大，那么我们把写着数x的格子拆成x个点，本来连接着数x和y的一条线就变成了拆成了x*y条线。这样就是二分图的独立数了。但是这样做复杂度太高，实际上这个匹配数就等于不拆点前的最大流量。这样就不和数的范围有关了。

2.5.18 团队分组

对于第1个人，由于一共只有两个组，所以不妨设他在第1组。如果他和所有人认识，那么可以不考虑他，把其他组分好以后再加进去。否则假设有一个人x和他不认识，显然x必须在第2组。对于所有1不认识的人，我们都可以把他们丢进第2组，同样对于第2组中某人不认识的，我们也可以丢进第1组，直到没有办法再加入其他元素，这时算法告一个段落。剩下的重新开始，又得到新的两组，现在需要把两组进行合并，应当借助动态规划。

2.5.19 调皮的导盲犬

而且一个地方最多只能玩一次，所以我们很 由于狗每次离开主人最多只能选一个地方，

容易建立一个二分图模型：左边是顶点集合A，表示狗某次离开主人；右边是顶点集合B，表示好玩的地方；边（x,y）表示狗第x次离开主人可以去好玩的地方y。问题要求的即是集合A与集合B的最大二分图匹配。

算法艺术与信息学竞赛习题部分提示…… 此处隐藏：2270字，全部文档内容请下载后查看。喜欢就下载吧 ……