数据结构 图的应用及其实现.docVIP

实验六 图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 二.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)） 【题目三】高速公路描述 某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。 输入 输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。 输出 输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。 样例输入 3?31?2?100 2?3?100 1?3?50 2 1?3 2?3 样例输出 100100 【题目四】 最短的旅程 描述 在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。?一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。???????? Starhder —— 就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。?于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。 输入 第一行包含两个整数，上文中的n和k，以一个空格隔开。（2= n =50000，1 = k =n）?下面的n- 1行每行描述一条路，第i + 1行包含3个整数ai，bi，di，相邻两个数用一个空格隔开（1= ai,bi = n，1= di = 1000），ai和bi是用道路直接相连的城市编号，di是这条道路的长度。?第n + 1行包含一个整数j，是starhder要旅游的城市数（1= j = n - 1），接下来一行包含j个不同的整数m1，m2，……，mj，每两个相邻的整数用一个空格隔开，表示starhder想要去的城市。（1= mt=n，mt k）。 输出 输出只有一行，包含一个整数：starhder旅游的最短路程。 样例输入 4?21?2?1 4?2?2 2?3?3 2 1?3 样例输出 5 连通 OR 不连通描述 D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 n,m（5=n=40000,1=m=100000） 接下来m行，每行一对整数 x y （x,y=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 Q操作的回答，连通的回答C，不连通的回答D 样例输入 3?31?21?32?35Q?1?2D?1?2Q?1?2D?3?2Q?1?2 样例输出 CCD An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of th