#P2625. [Neerc2009]Inspection

    ID: 1680 传统题 1000ms 512MiB 尝试: 91 已通过: 28 难度: 7 上传者: 标签>CF2300提高+/省选-上下界最小流下界转化超级源汇Dinic残量网络路径恢复

[Neerc2009]Inspection

题目描述

你负责一个团队来检查一个新的滑雪度假村。滑雪度假胜地坐落在几座山上,由许多坡道组成。

坡道之间相互连接,分叉和汇聚。滑雪度假村的地图可表示为一个无环有向图。

图的节点代表滑雪度假胜地中的不同点,图的边表示连通这些点的坡道,边的方向是向下的。

你的团队必须检查滑雪度假胜地的每一条坡道。这个度假村的滑道还没有开放,但是你们有一架直升飞机。

在一次飞行中,直升机可以把一个人投放到度假村的任何一个点上。从投放点出发,这个人可以滑下坡道,检查每个坡道。重复检查同一坡道是可以接受的,但你必须最小化直升机的使用。

因此,你必须弄清楚如何以最少的直升机飞行次数来检查所有的坡道。

简易题面

给张有向无环图,问至少多少条路径能够覆盖所有的边(可以重复)。

输入格式

输入文件的第一行包含一个整数 nn,表示滑雪度假村中的点数。

接下来的 nn 行描述滑雪度假村的每个点,编号从 11 到 nn。

每行以一个整数 mim_i 开始(对于ii从 11 到 nn 有 0≤mi<n0 \leq m_i < n),后跟 mim_i个用空格分隔的整数 ai,ja_{i,j}。

对于每个 ii 和每个 ai,ja_{i,j} 都是不同的,它们分别表示从点 ii 到 ai,ja_{i,j} 的向下的坡度。每个度假村的点至少有一条与其相连的坡度。

输出格式

在输出文件的第一行写入一个整数 kk,表示检查所有坡道所需的最小直升机飞行次数。

然后写入 kk 行,描述每次直升机飞行的检查路线。每个路线应从 11 到 nn 的单个整数开始,表示直升机飞行的投放点的编号,后跟按照检查的坡道相应的顺序访问的点编号。

每行上的数字应由空格分隔。您可以以任何顺序编写路线。

8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
4

数据规模与约定

对于 100%100\% 的数据,2≤n≤1002 \leq n \leq 100,1≤ai,j≤n1 \leq a_{i,j} \leq n。

题目来源

Neerc2009