数据结构图复习试题（一）
第一题：医院设置
问题描述：
设有一颗二叉树，如图5-1：
其中，图中的数字表示节点中居名的人口。圈边上数字表示节点编号，现在要求在某个节点上建立一个亿元，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。
如上图中，若医院建在：
1处，则距离和=4+12+2*20+2*40=136
3处，则距离和=4*2+13+20+40=81
……
输入：
第一行一个整数n，表示树的结点数。（n<=100）
接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。
输出：
一个整数，表示最小距离和。
样例：
hospital.in
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
hospital.out
81
第二题：宫廷守卫
问题描述：
从前有一个王国，这个王国的城堡是一个矩形，被分为M*N个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。
一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了。守卫们只能被布置在空地上，不能被布置在陷阱或墙上，且一块空地只能布置一个守卫。如果两个守卫在同一行或同以劣，并且他们之间没有墙的话，他们就能互相看见。（守卫就像象棋里的车一样）
你的任务是写一个程序，根据给定的城堡，计算最多可布置多少个守卫，并设计出布置的方案。
输入：
第一行两个整数M和N(1<=M，N<=200)，表示城堡的规模。
接下来M行N列的整数，描述的是城堡的地形。第i行j列的数用ai,j表示。
ai,j= 0，表示方格[i，j]是一块空地；
ai,j= 1，表示方格[i，j]是一个陷阱；
ai,j= 2，表示方格[i，j]是墙。
输出：
第一行一个整数K，表示最多可布置K个守卫。
样例：
guards.in
3 4
2 0 0 0
2 2 2 1
0 1 0 2
guards.out
2
样例数据如图5-2（黑色方格为墙，白色方格为空地，圆圈为陷阱，G表示守卫）
G
G
第三题： 公路修建
问题描述：
某国有n个城市，他们互相之间没有公路相通，因此交通十分不便，为解决这一“行路”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。
修建公路分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下：
（1）如果两个或以上城市申请修建同一条公路，则让他们共同修建。
（2）如果三个或以上的城市申请修建的公路成环。如下图，A申请修建公路AB，B申请修建公路BC，C申请修建公路CA。则政府将否决其中最短的一条公路的修建申请；
（3）其他情况的申请一律同意。
一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时，修建工作也就完成了。
你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。
输入：
第一行一个整数n，表示城市的数量。（n<=5000）
以下n行，每行两个整数x和y，表示一个城市的坐标。（-1000000<=x，y<=1000000）
输出：
一个实数，四舍五入保留两位小树，表示公路总长。（保证有惟一解）
样例：
road.in
4
0 0
1 2
-1 2
0 4
road.out
6.47
修建的公路如图所示：
速度限制
问题描述：
在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。
你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地A和B，最多只有一条道路从A连接到B。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。
输入：
输入文件speed.in的第一行是3个整数N，M和D（2<=N<=150），表示道路的数目，用0..N-1标记。M是道路的总数，D表示你的目的地。接下来的M行，每行描述一条道路，每行有4个整数A（0<=A<N），B（0<=B<N）,V(0<=V<=500)and L，(1<=L<=500)，这条路是从A到B德，速度限制是V，长度为L。如果V是0，表示这条路的限速未知。如果V不为0，则经过该路的时间T=L/V。否则T=L/Vold ， Vold 是你到大概路口前的速度。开始时你位于0点，并且速度为70。
输出：
输出文件speed.out仅一行整数，表示从0到D经过的城市。
输出的顺序必须按照你经过这些城市的顺序，以0开始，以D结束。仅有一条最快路线。
样例：
speed.in
6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40
speed.out
0 5 2 3 1
