最小路径覆盖算法-Dinic算法+代码.docx

最小路径覆盖问题一．问题描述：给定有向图 G=(V,E)。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个顶点恰好在 P 的一条路上，则称 P是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。?　设计一个有效算法求一个有向无环图G 的最小路径覆盖。二．编程任务：对于给定的给定有向无环图G，编程找出 G的一个最小路径覆盖。三．数据输入与输出：由文件input.txt提供输入数据。文件第1 行有 2个正整数 n和 m。n是给定有向无环图G 的顶点数， m是G 的边数。 接下来的m行， 每行有 2 个正整数 i和 j， 表示一条有向边(i,j)。程序运行结束时，将最小路径覆盖输出到文件 output.txt 中。从第 1 行开始，每行输出一条路径。文件的最后一行是最少路径数。 [输入输出]: [样例]: Sample Input11 12?1 2?1 3?1 4?2 5?3 6?4 7?5 8?6 9?7 10?8 11?9 11?10 11?Sample Output1 4 7 10 11?2 5 8?3 6 9?3四．分析与设计（1）分析问题最小路径覆盖问题：用尽量少的顶点不相交（如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边）简单路径覆盖有向无环图的所有顶点。对于路径覆盖中的每条连接两个顶点之间的每条有向边pi-pj ，我们可以在匹配图中对应做一条连接pi与pj的边 ，这样做出来图的就是一个匹配图。原图的路径覆盖和新图的匹配间有对应关系：路径要求不能相交，恰好对应于匹配中两匹配边不能有公共端点。说明：如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边 pi---pj 及 pi ----pk，（j!=k），那么在路径覆盖图中就存在了两条边pi--pj, pi---pk ，那边从pi出发的路径就不止一条了 ，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi---pj ,pk---pj ，这种情况也类似可证I：于是求最大匹配后，每条覆盖边都是匹配中的一条边，不能匹配上的点，即是路径的最后一个点。有多少个不能被匹配的点，就有多少条路径存在。II：如果匹配数为零，那么不存在有向边，于是显然有最小路径覆盖=节点数；如果在P中增加一条匹配边pi-pj ，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个； 如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式。III：一个点也是一条路径。若点没有匹配的话，单独的一个点也是一条路径。路径数=原点数－匹配边数。因此我们使匹配边数最大，得到的路径数也就最小。（2）问题设计与解答：按照问题的分析，建立网络最大流模型解此问题。I：把每个点拆分成 2 个点 Xi, Yi，由 s 向 Xi 引弧，Yi 向 t 引弧，如果 Xi, Yj 存在弧则引弧。所有弧的容量均为 1。 II：这样就构造出来了二分图的模型，然后求最大流即是这个二分图的最大匹配了。路径数 = 点数 – 最大匹配。III：因为如果存在一个匹配边，则被覆盖的点数就会减 1，所以此时路径数就是如 2 中求得。（3）Dinic算法求增广路径在求增广路径时，由于BFS寻找终点太慢，但是DFS又不能保证找到最短路径，当然，如果中和一下，构造分层网络的方法就可以找到比较快的最短增广路，（阻塞流算法），其基本思路是： 1.根据残量网络计算层次图； 2.在层次图中使用DFS进行增广直到不存在增广路； 3.不断重复直到无法增广的时候，算法结束。所谓的层次图，在残量网络中从源点S起始进行BFS，这样每个顶点在BFS树中就会得到一个距源点s的距离d , 如果d(s) = 0，直接从s出发可以到达的点距离为1，下一层距离为2……把具有相同距离的顶点放在同一层，在层次图中，只保留d(i) + 1 = d(j) 的边，这样在层次图中的任意路径就成为到达次顶点的最短路径。在Dinic算法中，BFS的作用就是判断找的汇点是否在源点开始的层次图中，之后就是在层次图中使用DFS进行增广。如果找到一个节点在层次图中，用它往下延伸，一直延伸到汇点，如果存在，就在这条路上找最小容量，增广之；如果增广之后，容量满了，阻塞之，实现方法即把这个点在层次图里的编号赋为其它点到不了的值，比如INT_MAX，-1。如果不能到达汇点，这个节点返回上一层，继续找。如果这个点都找完后（即上一层到达源点），再BFS从源点建立新的