

$3.$最小路径覆盖问题

题目

给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上，则称 $P$是 $G$ 的一个路径覆盖。$P$ 中路径可以从$V$ 的任何一个顶点开始，长度也是任意的，特别地，可以为0。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。提示：设 $V={1，2，.... ，n}$，构造网络 $G1=(V1,E1)$ 如下：

题解

直接按照提示中的去做，将每个点 $i$ 拆成 $x[i]$ 放左边, $y[i]$ 放右边。 $S$ 先向左边集合连边，右边向 $T$ 连边，若原图中存在一条边 $(u,v)$,则建一条边 $(x[u], y[v])$， 所有边流量为 $1$，然后跑最大流出来二分图最大匹配数，点数减最大匹配数就是最少路径条数，如何输出也很简单，直接按照匹配边走就行。 正确性显然，可以自己想一下。