洛谷 P2764 最小路径覆盖问题

题面

题目传送

给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个定点恰好在$P$的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。$P$中路径可以从 $V$ 的任何一个定点开始,长度也是任意的,特别地,可以为 $0$ 。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) $G$ 的最小路径覆盖。
提示:设 $V=\{1,2,…,n\}$ ,构造网络 $G_1=\{V_1,E_1\}$ 如下: $$V_1=\{x_0,x_1,…,x_n\}\cup\{y_0,y_1,…,y_n\}$$ $$E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\}$$ 每条边的容量均为 $1$ ,求网络 $G_1$ 的 $(x_0,y_0)$ 最大流。
一句话题面:给出一张图,用 $k$ 条链去覆盖它,求出最少的链数和覆盖方案。

输入输出格式

输入格式

第一行有 $2$ 个正整数 $n$ 和 $m$ 。 $n$ 是给定$\text{GAP}$(有向无环图) $G$ 的顶点数, $m$ 是 $G$ 的边数。接下来的 $m$ 行,每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。

输出格式

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

思路

对于一个点 $i$,将其拆成 $x_i,y_i$ 两个点。所有 $x_i$ 连接源点 $S$,所有 $y_i$ 连接汇点 $T$。

对于一条边 $(u,v)$,连边 $x_u,x_v$。

现在这张图变成了一张二分图,二分图中,最小路径覆盖 = 点的总数 – 网络最大流

最后从 $S$ 到 $T$ 跑一遍最大流。

证明

选出 $k$ 条链,也就是选出 $k$ 个集合,每个集合中的点的度数最多为 $2$。

对于一个点 $i$,当边 $(S,x_i)$ 和 $(y_i,T)$ 都被用掉时,这个点就不可能再被选,这就保证了每个点度数最多为 $2$。增广路只会经过两个节点,在同一集合中。

代码

 

暂无评论

发送评论


				
上一篇
下一篇