P2770 航空路线问题

    • 230通过
    • 972提交
  • 题目提供者 yyy2015c01 管理员
  • 评测方式 云端评测
  • 标签 网络流 网络流24题 O2优化 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一张航空图,图中顶点代表城市,边代表 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 也有一条直通航线。

    输出格式:

    件第 1 行是旅行路线中所访问的城市总数 M。 接下来的 M+1 行是旅行路线的城市名,每行写 1 个城市名。首先是出发城市名,然后按访问顺序列出其它城市名。 注意,最后 1 行(终点城市)的城市名必然是出发城市名。如果问题无解,则输出“No Solution!”。

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    7
    Vancouver
    Edmonton
    Montreal
    Halifax
    Toronto
    Winnipeg
    Calgary
    Vancouver 

    说明

    感谢 @FlierKing 提供spj

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。