Pro.ID1630 Title航空路线 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1630 AC0 Submit0 Ratio- 时间&空间限制描述给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。 输入第一行有两个正整数 N 和 V，N 表示城市数，V 表示直飞航线数。对于所有数据，N < 100 接下来的 N 行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设 i, j 是城市表列中城市出现的位置次序，当 i > j 时，表示 城市 i 在城市 j 的东边，而且不会有两个城市在同一条经线上。城市名是一个长度不超过 15 的字符串，串中的字符可以是大小写字母或阿拉伯数字。例如，AGR34 或 BEL4。 再接下来的 V 行中，每行有两个城市名，中间用空格隔开，如 city1 city2 表示 city1 到 city2 有一条直通航线，从 city2 到 city1 也有一条直通航线。 输出Description 给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。 Input 第一行有两个正整数 N 和 V，N 表示城市数，V 表示直飞航线数。对于所有数据，N < 100 接下来的 N 行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设 i, j 是城市表列中城市出现的位置次序，当 i > j 时，表示 城市 i 在城市 j 的东边，而且不会有两个城市在同一条经线上。城市名是一个长度不超过 15 的字符串，串中的字符可以是大小写字母或阿拉伯数字。例如，AGR34 或 BEL4。 再接下来的 V 行中，每行有两个城市名，中间用空格隔开，如 city1 city2 表示 city1 到 city2 有一条直通航线，从 city2 到 city1 也有一条直通航线。 Output 输出最佳航空旅行路线。 第一行是旅行路线中所访问的城市总数 M。 接下来的 M+1 行是旅行路线的城市名，每行一个。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后一行（终点城市）的城市名必然是出发城市名。如果有多组最优解，输出任意一组均可；如果问题无解，则输出 No Solution!。 Sample Input 8 9 Sample Output 7 Source 样例输入8 9 样例输出7 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 02:34 , Processed in 0.024158 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
