【网络流24题】最小路径覆盖问题

2014年2月28日5,0480

Description

问题描述:

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

编程任务:

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

Input Format

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

Output Format

从第1 行开始,每行输出一条路径(行末无空格)。文件的最后一行是最少路径数。

Sample Input

Sample Output

将每个点都分别放入xy集合中

如果u到v有一条边,则x集合的u向y集合的v连一条权值inf的边

S向x集合的点连边,权值1,y集合的点向T连边,权值1,做一遍最大流,得出最大匹配数

ans=n-最大匹配

如果无匹配,显然要n条路径才能覆盖所有点,两个点匹配意味着将可以把它们用一条路径覆盖,路径数就可以减1