【网络流24题-洛谷P2764 最小路径覆盖问题】

传送门

最小路径覆盖问题

题目描述

«问题描述:

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

\(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_0,y_i):i\in V\}\cup\{(x_i,y_i):i\in E\}\)

每条边的容量均为1。求网络G1的( 0 x , 0 y )最大流。

«编程任务:

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:

输出样例#1:

说明

1<=n<=150,1<=m<=6000

由@FlierKing提供SPJ

拆点+最大流+二分图匹配。

注意到每条路径有以下两个性质:

1.每个点仅包含在一条路径中

2.除了路径中的起点和终点,其余每个点都一定是一条边的到达点、一条边的出发点

因此,我们可以将一个点拆成两个点来做,即拆成代表从这个点出发的点集合\(X\)与代表到达这个点的点集合\(Y\),建立超级源点\(S\)与超级汇点\(T\),\(S\)到所有\(X\)集合中的点连一条边,\(Y\)中所有的点到\(T\) 连一条边,\(X\)与\(Y\)集合中的点按照原图关系来连边(比如对点\(u\),\(u\)代表从它出发,\(u+n\)代表到达它,则对于原图中的边\((u,v)\),建一条\(u,v+n\)的边),将所有边容量设定为1,跑一次最大流,最少路径条数就是顶点数\(-\)最大匹配数(最大流)。

原理:路径条数=顶点数-匹配数(比如开始11个点每个都是一条长度为0的路径,有11条路径,之后你每连一条边,新增一组匹配,路径的条数就-1),因此要让路径条数最小,即匹配数最大,问题转化为求二分图的最大匹配数,也就是最大流。

匹配时记录一下匹配边,双向记录,输出路径时,先找到没有前向边的点,从这个点开始,按照匹配边一路找下去就得到了每条路径。

PS:本题数据非常水,而且样例很误导人,即使是直接枚举1~n,从没输出过的点开始输出路径仍然可以AC,但是这种输出路径法是错的,因为若一个点没有输出,它可能是某条路径的中间点,而必须找到起点才能保证正确输出路径!

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*