网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[网络流24题]航空路线
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | airl.in | 输出文件 | airl.out |
«问题描述:
给定一张航空图,图中顶点代表城市,边代表2城市间的直通航线。现要求找出一条满
足下述限制条件的且途经城市最多的旅行路线。
(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东
向西飞回起点(可途经若干城市)。
(2)除起点城市外,任何城市只能访问1次。
«编程任务:
对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。
«数据输入:
由文件airl.in提供输入数据。文件第1 行有2个正整数N 和V,N 表示城市数,N<100,
V 表示直飞航线数。接下来的N行中每一行是一个城市名,可乘飞机访问这些城市。城市名
出现的顺序是从西向东。也就是说,设i,j 是城市表列中城市出现的顺序,当i>j 时,表示
城市i 在城市j 的东边,而且不会有2 个城市在同一条经线上。城市名是一个长度不超过
15 的字符串,串中的字符可以是字母或阿拉伯数字。例如,AGR34或BEL4。
再接下来的V 行中,每行有2 个城市名,中间用空格隔开,如 city1 city2 表示city1
到city2 有一条直通航线,从city2 到city1 也有一条直通航线。
«结果输出:
程序运行结束时,将最佳航空旅行路线输出到文件airl.out 中。文件第1 行是旅行路
线中所访问的城市总数M。接下来的M+1 行是旅行路线的城市名,每行写1 个城市名。首
先是出发城市名,然后按访问顺序列出其它城市名。注意,最后1行(终点城市)的城市名
必然是出发城市名。如果问题无解,则输出“No Solution!”。
输入文件示例 输出文件示例
airl.in
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver
给定一张航空图,图中顶点代表城市,边代表2城市间的直通航线。现要求找出一条满
足下述限制条件的且途经城市最多的旅行路线。
(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东
向西飞回起点(可途经若干城市)。
(2)除起点城市外,任何城市只能访问1次。
«编程任务:
对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。
«数据输入:
由文件airl.in提供输入数据。文件第1 行有2个正整数N 和V,N 表示城市数,N<100,
V 表示直飞航线数。接下来的N行中每一行是一个城市名,可乘飞机访问这些城市。城市名
出现的顺序是从西向东。也就是说,设i,j 是城市表列中城市出现的顺序,当i>j 时,表示
城市i 在城市j 的东边,而且不会有2 个城市在同一条经线上。城市名是一个长度不超过
15 的字符串,串中的字符可以是字母或阿拉伯数字。例如,AGR34或BEL4。
再接下来的V 行中,每行有2 个城市名,中间用空格隔开,如 city1 city2 表示city1
到city2 有一条直通航线,从city2 到city1 也有一条直通航线。
«结果输出:
程序运行结束时,将最佳航空旅行路线输出到文件airl.out 中。文件第1 行是旅行路
线中所访问的城市总数M。接下来的M+1 行是旅行路线的城市名,每行写1 个城市名。首
先是出发城市名,然后按访问顺序列出其它城市名。注意,最后1行(终点城市)的城市名
必然是出发城市名。如果问题无解,则输出“No Solution!”。
输入文件示例 输出文件示例
airl.in
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
airl.out
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver