| 题目名称 | 735. [网络流24题] 航空路线 |
|---|---|
| 输入输出 | airl.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-04-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：24， 通过率：0% | ||||
 毕之 |
20 | 0.004 s | 0.23 MiB | Pascal |
 lqwang1985 |
20 | 0.014 s | 0.34 MiB | Pascal |
|
毕之 |
20 | 0.033 s | 0.23 MiB | Pascal |
|
毕之 |
10 | 0.080 s | 0.16 MiB | Pascal |
 bolubolu |
0 | 0.000 s | 0.00 MiB | C++ |
 Mayuri |
0 | 0.000 s | 0.00 MiB | C++ |
 （ˇˍˇ） ～耶稣 |
0 | 0.000 s | 0.34 MiB | C++ |
|
lqwang1985 |
0 | 0.003 s | 0.34 MiB | Pascal |
 bbsh |
0 | 0.008 s | 0.69 MiB | C++ |
|
（ˇˍˇ） ～耶稣 |
0 | 0.009 s | 0.34 MiB | C++ |
| 关于 航空路线 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
题意明确 数据错!!!
此题依旧无法做 | ||||
|
这道题目的输入文件和输出文件有问题，没有对应正确。
lqwang1985
2013-12-24 17:17
1楼
| ||||
【题目描述】
给定一张航空图，图中顶点代表城市，边代表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 7 Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver