图论基本算法练习.pdf

JZOI2011冬令营A层次

图论基本算法练习

1．最优布线问题（wire.pas）

问题描述：学校有n台计算机，用数据线连接起来。现在由你负责连接这些计算机，你的任务是使

任意两台计算机都连通（无论是直接或是间接连接）

输入文件（wire.in）：

第一行是n（2=n=100）

表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计

算机和第y台计算机的费用。

输出文件(wire.out)：

一个整数，表示最小的连接费用。

样例：

输入：

3

012

101

210

输出：

2表示：1和2，2和3，最小费用2

2．小呆打车（taxi.pas）

题目描述：寒假里，小呆要去位于A市的皮球家拜年。小呆来到A市的车站，买了一张A市的地图，

他发现这里的地形非常的复杂。A市的街道一共有N个路口，M条道路，每条道路连接着两个路口，

并且有各自的长度。目前，小呆所在的车站位于编号为1的路口，而皮球家所在的路口编号为N，

小呆准备打出租车去，当然，路程越小，付的钱就越少。问题摆在眼前：请帮助小呆寻找一条最短

路径，使得他可以花最少的钱到达皮球家。

输入文件（taxi.in）：

输入文件的第一行有两个整数N;M,(N=1000=M)分别代表路口数和街道数。以下有M行用以

描述各个街道，每行有三个数字P1;P2;L,分别代表此街道起点编号，此街道终点编号以及此街道的

长度。保证所给的数据可以构成连通图。

输出文件（taxi.out）：

输出文件中只要求出现一行，一个整数，说明最短路径的长度(=maxlongint)。

样例：

输入：

67

121

135

142

4610

253

358

567

输出：

11

3．大战（war.pas）

背景介绍：木叶忍者村——拥有精锐忍者军团的最强忍者村在村子的村长[火影]的带领下，全体村民

团结的力量与许多优秀的忍者，让木叶忍者村变得非常繁荣，而且这也让村民有了在其他国家的民

众身上不太容易看到的爱国心。木叶忍者村的忍者们虽然活在严苛的忍者世界中，但是却都效忠村

子，而且还把村子里的人们当成自己的家人般喜爱与保护着，而在他国可能会受到迫害的拥有奇异

能力之人，在这个村子也不会受到差别待遇。这种自由的风俗造就了这个村子的繁荣。

问题描述：话说木叶要和死神开战了，他们打的那是天昏地暗，鬼哭狼嚎，地动山摇，炊烟袅袅升

起，这一仗造成人员大面积死亡，只剩余=3万人还活在战场上，为了了解大战实况，你只身一人

进入大战阵营，你会选择一条简单的路径，不过由于大战，好多路都封死了，在完好的路中也有危

险系数，你当然要选危险小的走，不过，为了了解全部实况，你必须拜访所有的人。

输入文件（war.in）：

nm(n表示人数，m表述路的条数。注意：两点间路不止一条）

xyz(一共m行，每行3个数，分别表示从x到y的危险系数为z=0)

（注意：没有出现的就表示不通）

输出文件（war.out）：

最小危险系数

样例：

输入：

47

12477

23267

340

21137

21564

31408

34152

输出：

404

数据范围：

30%n=2000m=8000

60%n=10000m=20000

100%n=30000m=50000

4．病毒（virus.pas）

问题描述：有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，

只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。

现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若

干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故

意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复

其它文档。

现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。

输入文件（virus.i