首页 > 题解 > 网络流24题之三 最小路径覆盖问题

网络流24题之三 最小路径覆盖问题

填坑

地址:luogu2764

题目描述

«问题描述:

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

images

 

每条边的容量均为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

模型:

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

实现:

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

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

分析:

对于一个路径覆盖,有如下性质:

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

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

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

代码:

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×