#P2770. 航空路线问题

    ID: 5084 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>网络流Special JudgeO2优化网络流 24 题

航空路线问题

题目描述

给定一张航空图,图中顶点代表城市,边代表两城市间的直通航线,并且不存在任何两个城市在同一条经线上。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

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

  2. 除起点城市外,任何城市只能访问一次。

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

输入格式

输入的第一行是用空格隔开的两个整数,分别代表航空图的点数 nn 和边数 vv

22 到第 (n+1)(n + 1) 行,每行一个字符串,第 (i+1)(i + 1) 行的字符串代表从西向东第 ii 座城市的名字 sis_i

(n+2)(n + 2) 到第 (n+v+1)(n + v + 1) 行,每行两个字符串 x,yx, y,代表城市 xx 和城市 yy 之间存在一条直通航线。

输出格式

本题存在 Special Judge

请首先判断是否存在满足要求的路线,若存在,请给出一种旅行的方案。

如果存在路线,输出格式为:

  • 请在第一行输出一个整数 mm,代表途径最多的城市数。
  • 在第 22 到第 (m+1)(m + 1) 行,每行一个字符串,第 (i+1)(i + 1) 行的字符串代表旅行路线第 ii 个经过的城市的名字。请注意第 11 和第 mm 个城市必然是出发城市名。

否则请输出一行一个字符串 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 Calgary
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver 

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n<1001 \leq n < 1001vn×(n1)21 \leq v \leq \frac{n \times (n - 1)}{2}sis_i 的长度不超过 1515,且仅可能包含大小写字母与数字,x,yx, y 一定是输入中给出的城市名,且不会有同一组 x,yx, y 被给出两次。