【问题分析】

有向无环图最小路径覆盖，可以转化成二分图最大匹配问题，从而用最大流解决。

【建模方法】

构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。

最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。

【建模分析】

对于一个路径覆盖，有如下性质：

1、每个顶点属于且只属于一个路径。 2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

最小路径覆盖问题
问题描述: 给定有向图 G=(V,E)。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶 点开始,长度也是任意的,特别地,可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少 的路径覆盖。
设计一个有效算法求一个有向无环图 G 的最小路径覆盖。 提示:设 V={1,2,o ,n},构造网络 G1=(V1,E1)如下:
V1 = {x0 , x1 ,, xn }» {y0 , y1 ,, yn },
E 1 = {( x 0 , x i ) : i Œ V } » {( y i , y 0 ) : i Œ V } » {( x i , y j ) : ( i . j ) Œ E } 每条边的容量均为 1。求网络 G1 的( x0 , y0 )最大流。
 ́编程任务: 对于给定的给定有向无环图 G,编程找出 G 的一个最小路径覆盖。  ́
数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 n 和 m。n 是给定有向无环图G 的顶点数,m 是 G 的边数。接下来的 m 行,每行有 2 个正整数 i 和 j,表示一条有向边(i,j)。  ́
结果输出:
程序运行结束时,将最小路径覆盖输出到文件 output.txt 中。从第 1 行开始,每行输出 一条路径。文件的最后一行是最少路径数。
输入文件示例
input.txt
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
输出文件示例
output.txt
1 4 7 10 11
2 5 8
3 6 9
3

上次修改时间 2017-02-03