2934. 航空路线问题

单点时限: 2.0 sec

内存限制: 256 MB

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

(1) 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点 (可途经若干城市)。

(2) 除起点城市外,任何城市只能访问 1 次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

输入格式

文件第 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 也有一条直通航线。

输出格式

输出旅行路线中所访问的城市总数 M,如果问题无解,则输出 “No Solution!”。

样例

Input
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
Output
7

4 人解决,7 人已尝试。

5 份提交通过,共有 27 份提交。

8.1 EMB 奖励。

创建: 13 年,11 月前.

修改: 2 年,5 月前.

最后提交: 6 年,7 月前.

来源: zzz-周正中

题目标签