给定有向图 G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个定点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个定点开始,长度也是任意的,特别地,可以为 0 。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图 G 的最小路径覆盖。
输入格式
第一行有 2 个正整数 n 和 m 。n 是给定有向无环图 G 的顶点数,m 是 G 的边数。接下来的 m 行,每行有两个正整数 i 和 j 表示一条有向边 (i,j)。
设原来的有向无环图为 G=(V,E),n=∣V∣。把 G 中的每个点 x 拆成编号为 x 和 x+n 的两个点。建立一张新的二分图,1n 作为二分图左部点,n+1∼2n 作为二分图右部点,对于原图的每条有向边 (x,y),在二分图的左部点 x 与右部点 y+n 之间连边。最终得到的二分图称为 G 的拆点二分图,记为 G2。
不加证明地给出定理:有向无环图 G 的最小路径点覆盖包含的路径条数,等于 n 减去拆点二分图 G2 的最大匹配数;最小路径覆盖中的所有边,在拆点二分图 G2 中构成一组匹配。最小路径覆盖中每条边 (x,y) 的起点 x 与二分图每条匹配边 (x,y+n) 的左部点 x 是一一对应的。
因此,对一个有向无环图,可建立拆点二分图,利用匈牙利算法求最大匹配,并且可以利用 match 数组输出匹配方案。