[AdditionalFile4912.zip](file://AdditionalFile4912.zip?type=additional_file)

P3561 [POI 2017] Turysta

题目描述

给出一个 $n$ 个点的有向图，任意两个点之间有且仅一条有向边。

对于每个点 $v$，求出从 $v$ 出发的一条经过点数最多，且没有重复经过同一个点两次及两次以上的简单路径。

输入格式

第一行包含一个正整数 $n$，表示点数。

接下来的 $n-1$ 行，其中的第 $i$ 行有 $i-1$ 个数。

如果第 $j$ 个数是 $1$，那么表示有向边 $j\rightarrow i+1$ ，如果是 $0$，那么表示有向边 $j\leftarrow i+1$。

输出格式

输出 $n$ 行，第 $i$ 行首先包含一个正整数 $k$，表示从 $i$ 点出发的最优路径所经过的点数。

接下来 $k$ 个正整数，依次表示路径上的每个点。

若有多组最优解，输出任意一组。

本题使用 SPJ （Claris 制作）

输入输出样例 #1

输入 #1

4
1
1 1
1 0 1

输出 #1

4 1 2 3 4
3 2 3 4
3 3 4 2
3 4 2 3

说明/提示

对于 $100\%$ 的数据，$2\le n\le 2 \times 10^3$。

#4912. 「POI2017 R1」游客 Tourist

标签: 传统 | 时间限制: 8000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Turysta

字节城曾经是个美丽、交通便利的国家，每座城市之间都有双向直达道路。可惜，比特城发动战争，用「比特城极化磁铁」把所有道路变成了单向。战争虽已结束，但磁铁的影响让字节城的交通陷入混乱。

著名旅行家朗金特先生战前计划游遍字节城所有城市。现在这可能行不通，他只能尽量多逛几座城。请你写个程序，为他从每座可能的起点城市规划一条路线，尽可能多地游览不同城市，且每座城只经过一次。假设朗金特先生可在任意城市结束旅程。

输入格式

输入第一行是一个整数 $n$ $(2 \leq n \leq 2000)$，表示字节城的城市数量，城市编号从 $1$ 到 $n$。

接下来的 $n-1$ 行描述当前道路状况。第 $i$ 行描述编号为 $i+1$ 的城市与之前所有城市的连接，包含 $i$ 个数字（$0$ 或 $1$）。若第 $j$ 个数是 $1$，则道路从 $j$ 号城市通向 $i+1$ 号城市；若为 $0$，则方向相反，从 $i+1$ 到 $j$。

输出格式

输出 $n$ 行，第 $i$ 行描述从 $i$ 号城市出发、访问最多不同城市（每城仅一次）的路线。

每行开头是一个整数 $d \geq 1$，表示路线上的城市数，后面跟 $d$ 个整数，表示朗金特先生依次访问的城市编号。若有多条最长路线，输出任意一条即可。

样例

输入

4
1
1 1
1 0 1

输出

4 1 2 3 4
3 2 3 4
3 3 4 2
3 4 2 3

附加样例

1. $n=3$，形成环路；
2. $n=2000$，每条路都指向编号较小的城市。

数据范围与提示

详细子任务附加限制及分值如下表所示。