P3549 [POI2013]MUL-Multidrink

    • 0通过
    • 2提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 图论 构造 POI 2013 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Byteasar lives in Byteburg, a city famous for its milk bars on every corner.

    One day Byteasar came up with an idea of a "milk multidrink": he wants to visit each milk bar for a drink exactly once.

    Ideally, Byteasar would like to come up with a route such that the next bar is always no further than two blocks (precisely: intersections) away from the previous one.

    The intersections in Byteburg are numbered from to , and all the streets are bidirectional.

    Between each pair of intersections there is a unique direct route, ie, one that does not visit any intersection twice.

    Byteasar begins at the intersection no. and finishes at the intersection no. .

    Your task is to find any route that satisfies Byteasar's requirements if such a route exists.

    An exemplary route satisfying the requirements is: There is no route that satisfies the requirements.

    给一棵树,每次步伐大小只能为1或2,要求不重复的遍历n个节点,且起点为1,终点为n

    输入输出格式

    输入格式:

    In the first line of the standard input there is a single integer (), denoting the number of intersections in Byteburg.

    Each of the following lines holds a pair of distinct integers and (), separated by a single space, that represent the street linking the intersections no. and .

    In tests worth of all points the condition holds.

    输出格式:

    If there is no route satisfying Byteasar's requirements, your program should print a single word "BRAK" (Polish for none), without the quotation marks to the standard output. Otherwise, your program should print lines to the standard output, the -th of which should contain the number of the -th intersection on an arbitrary route satisfying Byteasar's requirements. Obviously, in that case the first line should hold the number , and the -th line - number .

    输入输出样例

    输入样例#1: 复制
    12
    1 7
    7 8
    7 11
    7 2
    2 4
    4 10
    2 5
    5 9
    2 6
    3 6
    3 12
    
    输出样例#1: 复制
    1
    11
    8
    7
    4
    10
    2
    9
    5
    6
    3
    12
    

    说明

    给一棵树,每次步伐大小只能为1或2,要求不重复的遍历n个节点,且起点为1,终点为n

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