2018年NOIP信息学奥赛提高组复赛C++真题day2

全国信息学奥林匹克联赛（ NOIP2018）复赛 提高组 day2 第1页共8页 CCF全国信息学奥林匹克联赛 （NOIP2018）复赛 提高组 day2 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 旅行 填数游戏 保卫王国 英文题目与子目录名 travel game defense 可执行文件名 travel game defense 输入文件名 travel.in game.in defense.in 输出文件名 travel.out game.out defense.out 每个测试点时限 1s 1s 2s 测试点数目 25 20 25 每个测试点分值 4 5 4 附加样例文件 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 运行内存上限 512MB 512MB 512MB 二．提交源程序文件名 对于C++语言 travel.cpp game.cpp defense.cpp 对于C语言 travel.c game.c defense.c 对于pascal语言 travel.pas game.pas defense.pas 三．编译命令（不包含任何优化开关） 对于C++语言 g++ -o travel travel.cpp -lm g++ -o game game.cpp -lm g++ -o defense defense.cpp -lm 对于C语言 gcc -o travel travel.c -lm gcc -o game game.c -lm gcc -o defense defense.c -lm 对于pascal语言 fpc travel.pas fpc game.pas fpc defense.pas 注意事项： 1、文件名（程序名和输入输出文件名） 必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为： Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存 32GB。上述时限以此配置为准 。 4、只提供 Linux格式附加样例文件。 5、特别提醒： 评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以其为准 。 全国信息学奥林匹克联赛（ NOIP2018）复赛 提高组 day2 第2页共8页 1．旅行 (travel.cpp/c/pas) 【问题描述】 小Y是一个爱好旅行的 OIer。她来到 X国，打算将各个城市都玩一遍。 小Y了解到，X国的 � 个城市之间有 � 条双向道路 。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市 。小Y只能通过这些 道路从一个城市前往另一个城市。 小Y的旅行方案是这样的： 任意选定一个城市作为起点，然后从起点开始， 每次可 以选择一条与当前城市相连的道路，走向一个 没有去过 的城市，