算法艺术与信息学竞赛习题解答

《算法艺术与信息学竞赛习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、缺少的提示：2.4.1;2.4.2;2.4.7;2.4.92.4.3Gridland其实这道题目只需要考虑两种情况。情况一：两个边长至少有一个是偶数长度为：2*(height-1)+2*(width-1)+(height-2)*(width-2)=2*height-2+2*width-2+height*width-2*height-2*width+4=height*width情况二：两个边长都是奇数长度为：Height*width–1+sqrt(2)因为少一条直边但是多一个斜边。2.4.4邮递员首先让我们把报酬的问题理清楚。如果期望值为Wi的村子是邮递员第Ki个经过的不

2、同村子，那么他会得到报酬Wi-Ki元；同时在邮递员走过所有M条路后，他会从邮局那里得到m元，所以无论邮递员怎么走，只要他完成了任务，报酬都是。这样报酬的问题就不用考虑了，需要解决的只剩如何完成任务。因为每个村子只可能处于两条路的十子路口上，或者四条路的米子路口上，或者一条路的中央，所以与每个村子相连的路的条数为偶数。这个村落的构造符合一笔画的充要条件，剩下的问题唯有求欧拉回路。2.4.5城市观光首先，完成所有旅程后的兴趣值为一定的。如果这个兴趣值小于0则必然不能满足要求，也就是说总的兴趣值大于0是路径存在的必要条件。那么是否有满足题意的充分条件呢？实际上，总的兴趣值大于

3、0就是路径存在的充分必要条件，构造如下：1.由于每个点的度都为4，所以图中必然存在欧拉回路，找出一条这样的欧拉回路。2.从任意一点出发，找到权最小的一个位置。如果这个位置的权是正的，则这条路经已经满足要求。3.因为这个权是最小的负权，设为-a(a>0)。所以从这个点出发，回到起点的权至少为a。而由于是最小负权，所以在从起点到这个点的这段路径中所有点的权都大于-a。换句话说，如果将这个权最小的点作为新起点，则从原起点到这个点的路径上的所有点的权均大于0。同时，由于这个点的权最小，所以在从这个点到起点的路径中所有的点的权也都大于0。满足题目要求。所以，只要构造出一条回路，就

4、总能在这条回路上找到一个点作为起点，满足题目要求。2.4.6赌博机我们来分析一下机器失败的苛刻条件。首先抽象模型：赌博机是图（称为图T1）中的顶点，如果赌博机x的集合中有一个数y，那么向图中添加一条从x指向y的有向边。仅当此图构成一个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路时，机器才有可能失败。所以下面我们只针对此种情况进行讨论：如果机器没有失败，那么图中剩余边构成残留图T3，机器运作路径构成图T2，T2是一个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路。因为T1-T2=T3，所以T3是顶点n入度出度皆为0其余

5、所有顶点入度等于出度的欧拉回路。既然是回路就必然包含圈，事实上，只要残留图T3是个圈而非没有边的空图，机器就不会失败。我们从每个顶点出发，找寻不包含顶点n的圈。如果找不到，那么机器失败；如果找到了，那么把这个圈从图T1中删除，剩下的图便是使得机器获胜的路径，而这个路径仍然是个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路。2.4.8远程通信例子给出的方案是怎样找到的呢？我们可以这样来分析：对于Bornholm端口2、Gotland端口1、Gotland端口4，由于没有其它端口以它们为目的端口，所以它们必须被设置成发送模式，因此一一对应的Gotl

6、and端口5、Bornholm端口4、Bornholm端口1必须为接收模式。删除由Gotland端口5、Bornholm端口4、Bornholm端口1发出的有向边。结果发现，由于边的删除，Gotland端口3、Bornholm端口3也成为只有发送模式没有接受模式的端口，所以它们必须被设置成发送模式，相应的Gotland端口2为接受模式。参照样例的解题方法，对于任意待匹配的通讯图，我们不断找出只有发送（接受）模式的端口x，确定它们以及相应接受（发送）端口y的运行方式，将点x、y及相关边从图中删除。如此迭代，直至无点、边可删。考虑当前剩余通讯图，图中共有a+b个点，a+b条

7、有向边，每个点入度出度皆为1。这样的图只能由若干个有向环构成。倘若某个有向环顶点个数为奇数，那么此通讯图无合法匹配方案；否则对于每个环任意确定某个端口为发送模式，其余端口的运行模式也就相应确定了。2.4.10龙穴迷宫图中部分点是重复的，于是想到不断把重复的点合并，以求出最少的点数。按F1的定义进一步定义Fk：描述以点k为起点到点n的路径，其中1≤k≤n，有：，显然，若，且，则可以将点与点合并，这样既减少了顶点数目又不会影响Fk，更不会改变F1。进而推广到更一般的情况，只要Fi=Fj，即可合并点i与点j。由于Fn至F1由简变繁，不难想到，从