最小路径覆盖

    网上的很多资料都是针对某道题目，有的甚至上来不做任何说明就直接上代码，费了我好大的时间才把基本的定义搞懂，这篇文章功不可没：http://hi.baidu.com/ufo008ahw/blog/item/363efdfd718e8443d7887de0.html，但是没有配上插图，第一遍理解起来还是有些困难。
    现在为了方便浏览，摘抄一下上面那篇文章的全文：
    在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．
    由上面可以得出：
    １.一个单独的顶点是一条路径；
    ２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．
    路径覆盖与二分图匹配的关系：
    最小路径覆盖＝|P|－最大匹配数
    其中最大匹配数的求法是把Ｐ中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在二分图Ｐ＇中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi的出边，pj''就是p中pj 的一条入边；
    对于公式：最小路径覆盖＝|P|－最大匹配数；可以这么来理解；
    如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：
    最小路径覆盖＝｜Ｐ｜－最大匹配数＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路径覆盖数为｜Ｐ｜；Ｐ＇中不在于匹配边时，路径覆盖数为｜Ｐ｜；如果在Ｐ＇中增加一条匹配边pi'－－＞pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个；如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只 是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边；与前面类似，对于路径覆盖中的每条连接两个顶点之间的每条有向边pi--->pj，我们可以在匹配图中对应做一条连接pi'与pj''的边， 显然这样做出来图的是一个匹配图（这一点用反证法很容易证明，如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边  pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路径覆盖图中就存在了两条边pi-->pj, pi--->pk ，那边从pi出发的路径就不止一条了，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi'---pj'',pk'---pj''，这种情况也类似可证）；至此，就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系，那么也就说明了前面的公式成立！

=================================================
    至此，看了这么一大段文字相信很多人都晕晕呼呼了，下面我用自己的话来做下解释，可能有的地方不是很严谨，但是还算比较容易理解吧。

   

    首先强调一条，原图中不能存在有向圈，否则程序直接退出，不能找出覆盖路径。
    上幅图的第一部分红色部分与蓝色部分就是两个路径覆盖，所以本图的最小路径覆盖数就为2。而上图的第二个部分是将每个点拆分之后的二分图，用Hungary算法简单跟一遍可知其最大匹配数为4（除去5`->3``这条边，剩下的4条边就是四个匹配）。
    最大匹配与最小路径覆盖有什么相同点呢？最小路径覆盖中，每个点只能属于一条路径，也就是说每个点的入度与出度最大为1，这与二分图中（P`代表P出度，P``代表P入度）不是很相似吗？所以这就是二者的相同或者说相似之处。
    但是真正的编程过程中需要分点吗？根据我的实践检验答案是不用的。
    原因如下：
    1，大家可以注意是上图的第二部分，点之间的连线我用的是有向边而不是无向边，仔细回想一下Hungary算法，根本不需要右侧点的回边，所有的边探索都是从左侧点开始的。所以根本不用按照原图在构造二分图，但这只是原因之一。

int hungary(int k)
{
    int i, j;
    for(i=1; i<= g[k][0]; i++)
    {
        j = g[k][i];
        if(!used[j])
        {
            used[j] = 1;
            if(!mat[j] || hungary(mat[j]))
            {
                mat[j] = k;
                return 1;
            }
        }
    }
    return 0;
}

    2，注意以上的Hungary算法，mat[]数组（记录和右侧点匹配的左侧点）只会用到右侧点所对应的单元，左侧根本不会用到（即mat[1`],mat[2`],mat[3`],mat[4`]……从始至终一直是0），所以真正用到的数组元素的个数仅仅和原图的顶点个数相等。
    综以上两点，原图根本不必拆分为二分图，而是直接送入Hungary函数进行运算即可。
    以上的观点也是受http://blog.chinaunix.net/u3/102624/showart.php?id=2060880的启发而来的。
    希望我表述的还算清楚。