P3443 [POI2006]LIS-The Postman

    • 0通过
    • 10提交
  • 题目提供者 远航之曲
  • 评测方式 云端评测
  • 标签 欧拉回路 POI 2006 Special Judge 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Each morning Byteasar the Postman has to visit every street of his district and deliver the mail. All of the roads are one-way and are connected by the (pairwise distinct) crossroads. A pair of crossroads may be connected by two roads at the most: one for each of the opposing directions. The crossroads are numbered from $1$ to $n$.

    Byteasar starts and ends each route in Byteotian Post headquarters, by the first crossroads. For as long as it can be remembered Byteasar had been choosing his route by himself, but recently the board of directors has issued a new regulation, limiting the freedom of choice of the routes. Each postman has been assigned a collection of route fragments - a set of sequences of crossroads. Byteasar has to choose such a route which:

    leads down each street once only, comprises each of the assigned sequences (as a consistent subsequence), starts and ends by the first crossroads.

    Unfortunately, it is possible that the board of directors issued a regulation, for which a route satisfying the requirements does not in fact exist (it requires in one of its sequences that a road be taken, which does not exist, for instance). Help Byteasar and write a programme which verifies if a correct route exists and finds it if it does.

    Task: Write a programme which:

    • reads from the input file a description of the streets and assigned sequences,

    • verifies if it is possible for Byteasar to get around his district in such a way as to allow him to visit each street exactly once and to fulfill the directors' assigment,

    • writes the route found to the output file or concludes that such a route does not exist.

    给定一个有向图,给定q个序列,询问是否存在一种行走方案使得从一点出发并且经过所有的边回到自己,并且该行走方案的序列包含了所有q个序列。

    输入输出格式

    输入格式:

    The first line of the input file contains two integers $n$ and $m$ separated by a single space, $2 \le n \le 50\ 000$, $1 \le m \le 200\ 000$, denoting the number of crossroads and roads, respectively.

    The following $m$ lines contain the descriptions of the roads: two integers $a$, $b$, separated by a single space, $1 \le a, b \le n, a \neq b$, denote a one-way road from the crossroads $a$ to $b$.

    Each (ordered) pair $a, b$ appears in the data once at the most. In the following line there is an integer $t$, $0 \le t \le 10\ 000$ , denoting the number of assigned sequences. The successive $t$ lines contain the descriptions of these sequences. A description consists of an integer $k$, $2 \le k \le 200\ 000$ , and a sequence $k$ of crossroads' numbers. The numbers in a line are separated by single spaces. The total length of all of the sequences does not exceed $100\ 000$.

    输出格式:

    Your programme should write in the first line of the output file:

    • TAK (i.e. yes in Polish) - if a route satisfying the requirements of the task exists,

    • NIE (i.e. no in Polish) - if such a route does not exist.

    Should the answer be TAK, the following lines should contain a description of the route found.

    Should more such routes exists, write out any of them. The description consists of the sequence of crossroads the postman visits while on his route - $m+1$ numbers: $v_1, ..., v_{m+1}$, each written out in a separate line, such that:

    • $v_1=v_{m+1}=1$

    • $v_i$ and $v_{i+1}$ (for $1 \le i \le m$) are connected by a street,

    • each street appears on the list once only,

    • the route comprises, as a consistent subsequence all of the sequences imposed by the board of directors.

    输入输出样例

    输入样例#1: 复制
    6 10
    1 5
    1 3
    4 1
    6 4
    3 6
    3 4
    4 3
    5 6
    6 2
    2 1
    4
    3 1 5 6
    3 3 4 3
    4 4 3 6 4
    3 5 6 2
    输出样例#1: 复制
    TAK
    1
    3
    4
    3
    6
    4
    1
    5
    6
    2
    1
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。