Preparing NOJ

最小路径覆盖问题

1000ms 65536K

Description:

 

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

的路径覆盖。

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

提示:设V={12¼ n},构造网络G1=(V1,E1)如下:

V1={x0,x1,…xn}{y0,y1,…yn},

E1={( x0,xi):iV}{( yi,y0):iV}{( xi,yj) ( i,j)E}

每条边的容量均为1。求网络G1的( 0 x , 0 y )最大流。

对于给定的给定有向无环图G,编程找出G的一个最小路径覆盖

Input:

 

文件第1 行有2个正整数nmn是给定有向无环图G 的顶点数,mG 的边数。接下来的m行,每行有2 个正整数ij,表示一条有向边(i,j)

Output:

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

Sample Input:

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

Sample Output:

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

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1350

Tags

Submitted 1

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet