航空路线问题(洛谷 - P2770)
说明
给定一张航空图，图中顶点代表城市，边代表两城市间的直通航线，并且不存在任何两个城市在同一条经线上。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
-
从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。
-
除起点城市外，任何城市只能访问一次。
对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表航空图的点数 n 和边数 v。
第 2 到第 (n+1) 行，每行一个字符串，第 (i+1) 行的字符串代表从西向东第 i 座城市的名字 si。
第 (n+2) 到第 (n+v+1) 行，每行两个字符串 x,y，代表城市 x 和城市 y 之间存在一条直通航线。
输出格式
本题存在 Special Judge。
请首先判断是否存在满足要求的路线，若存在，请给出一种旅行的方案。
如果存在路线，输出格式为：
- 请在第一行输出一个整数 m，代表途径最多的城市数。
- 在第 2 到第 (m+2) 行，每行一个字符串，第 (i+1) 行的字符串代表旅行路线第 i 个经过的城市的名字。请注意第 1 和第 m 个城市必然是出发城市名。
否则请输出一行一个字符串 No Solution!。
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 Calgary7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver 提示
数据规模与约定
对于 100% 的数据，保证 1≤n<100，1≤v≤2n×(n−1)，si 的长度不超过 15，且仅可能包含大小写字母与数字，x,y 一定是输入中给出的城市名，且不会有同一组 x,y 被给出两次。
原题链接