#P6002. 「网络流 24 题」最小路径覆盖

    ID: 126 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>Special Judge网络流最大流网络流 24 题

「网络流 24 题」最小路径覆盖

题目描述

给定有向图 G=(V,E) G = (V, E) 。设 P P G G 的一个简单路(顶点不相交)的集合。如果 V V 中每个顶点恰好在 P P 的一条路上,则称 P P G G 的一个路径覆盖。P P 中路径可以从 V V 的任何一个顶点开始,长度也是任意的,特别地,可以为 0 0 G G 的最小路径覆盖是 G G 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 G G 的最小路径覆盖。

输入格式

1 1 行有 2 2 个正整数 n n m m n n 是给定有向无环图 G G 的顶点数,m m G G 的边数。
接下来的 m m 行,每行有 2 2 个正整数 u u v v ,表示一条有向边 (i,j) (i, j)

输出格式

从第 1 1 行开始,每行输出一条路径。
文件的最后一行是最少路径数。

11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
1 4 7 10 11
2 5 8
3 6 9
3

数据范围与提示

1n200,1m6000 1 \leq n \leq 200, 1 \leq m \leq 6000