[NOI2006] 聪明的导游
题目背景
输入数据下载地址:
https://pan.baidu.com/s/1jJX0E3c
数据由1584432137提供。
Upd on 2022.8.7:输入文件在附件。
题目描述
小佳最近迷上了导游这个工作,一天到晚想着带游客参观各处的景点。正好 M 市在举行 NOI,来参观的人特别的多。不少朋友给小佳介绍了需要导游的人。
M 市有$n$个著名的景点,小佳将这些景点从$1$至$n$编号。有一些景点之间存在双向的路。小佳可以让游客们在任何一个景点集合,然后带着他们参观,最后也可以在任何一个景点结束参观。不过,来参观的游客们都不愿去已经参观过的地方。所以,小佳不能带游客们经过同一个景点两次或两次以上。
小佳希望你帮助他设计一个方案, 走可行的路线, 带游客们参观尽可能多的地方。
输入输出格式
输入格式
输入文件为 guide1.in~guide10.in,第一行为两个整数$n,m$,分别表示景点数和路的条数。接下来$m$行,每行两个整数$a,b$,表示景点$a$和景点$b$之间有一条双向路。
输出格式
你需要将答案输出到 guide1.out~guide10.out 中,guide?.out 为对应 guide?.in
的答案。输出的第一行为$p$,表示你能找到的路径所经过的景点个数。接下来$p$ 行,每行一个整数,按顺序表示你所找到的路径上的每一个景点。
输入输出样例
输入样例 #1
5 5
1 2
3 2
2 4
2 5
4 5
输出样例 #1
4
1
2
4
5
说明
【说明】
这是一道提交答案式的题目,你不需要提供任何源代码,只需要将自己的输出文件放在与*.in 同一个目录即可。
【样例说明】
题目可能有多解,该样例有 4 个解,你只需输出其中任何一个解。
|解$1$|解$2$|解$3$|解$4$|
| :----------: | :----------: | :----------: | :----------: |
|4 |4 |4 |4 |
|1 |1 |3 |3 |
|2 |2 |2 |2 |
|4 |5 |4 |5 |
|5 |4 |5 |4 |
【评分方法】
你的评分将由你的答案与标准答案之间的差异来给定。设你的答案正确且参观的景点数为 x,我们所给出的结果为 ans,则按下表计算你的得分:
|得分|条件|得分|条件|
| :-----------: | :-----------: | :-----------: | :-----------: |
|$12$ |$x>ans$ |$5$ |$x \leq ans \times 0.93$ |
|$10$ |$x=ans$ |$4$ |$x \leq ans \times 0.9$ |
|$9$ |$x \leq ans-1$ |$3$ |$x \leq ans \times 0.8$ |
|$8$ |$x \leq ans-2$ |$2$ |$x \leq ans \times 0.7$ |
|$7$ |$x \leq ans-3$ |$1$ |$x \leq ans \times 0.5$ |
|$6$ |$x \leq ans \times 0.95$ |$0$ |$x \leq ans < 0.5$ |
如果有多项满足,则取满足条件中的最高得分。