匈牙利算法

匈牙利算法是用来解决最大二分图匹配问题的，所谓二分图即 “一组点集可以分为两部
分，且每部分内各点互不相连，两部分的点之间可以有边”。所谓最大二分图匹配即  ”对于二分图的所有边，寻找一个子集，这个子集满足两个条件，
1：任意两条边都不依赖于同一个点。
2：让这个子集里的边在满足条件一的情况下尽量多。

 

匈牙利之前，先说说“增广轨”。
定义： 若P是图 G中一条连通两个未匹配顶点的路径，并且属最大匹配边集 M的边和不属M的边(即已匹配和待匹配的边)在 P上交替出现，则称P为相对于 M的一条增广轨 。

定义总是抽象的下面通过图来理解它。

                      
图中的线段（2->3,  3->1, 1->4）便是上面所说的 p路径， 我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配
的边，则边（4,1）边（1,3）和  边（3,2）  在路径p上交 替的出现啦，那么 p就是相对于M的一条增广轨，这样我们就可以用边1,4  和  边2,3 来替换边1,3  那么以匹配的边 集数量就可以加 1,。

 

匈牙利算法说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

 

每次我们从上面的第 i 个点出发尽量去找一个能唯一和它匹配的点 p，策略有两种，一是直接在下面的点中找到一个点 j，他没有和上面的点匹配过（即link[j]==-1）。二是当 j和上面的某个点匹配过，即（link[j]） 那么我们就从 match[j]出发，去给他找下面另外的点和他匹配，把j点留给点 i。这样我们不就多找到了一条？(增广路的路径长度必定为奇数，第一条边和最后一条边都不属于M。)

int map[N][N];//代表着关系ai...,an(上面的点)  ->bi...,bm(下面的点)
int useif[N];//useif[N]数组时标记第二部分点中的第j个点是否使用过
int link[N];//与第二部分中的点i匹配的点是link[N]
int can(int t)
{
    for(int j=1;j<=m;j++)
    {
        if(useif[j]==0 && map[t][j])
        {
            useif[j]=1;
            if(link[j]==-1 || can(link[j]))
            {
                link[j]=t;
                return 1;
            }
        }
    }
    return 0;
}

int maxmatch()
{
    int i,num;
    num=0;
    memset(link,-1,sizeof(link));
    for(i=1;i<=n;i++)
    {
        memset(useif,0,sizeof(useif));
        if(can(i))
            num++;
    }
    return num;
}

匈牙利算法就是同过不断的寻找增广轨实现的。很明显如果二分图的两部分点分别为 n
m，那么最大匹配的数目应该小于等于 MIN（n,m）;  因此我们可以枚举任第一部分（的
部分也可以）里的每一个点，我们从每个点出发寻找增广轨，最后把第一部分的点找完以
，就找到了最大匹配的数目，当然我们也可以通过记录找出这些边。
面给出关于二分图最大匹配的两个定理
                       1:最大匹配数  +  最大独立集  = n + m
                       2:二分图的最小覆盖数  =  最大匹配数
                       3:最小路径覆盖  =  最大独立集
最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。
最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。
最小路径覆盖是指一个不含圈的有向图G 中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P 中的某一条路径。路径可以从任意结点 开始和结束，且长度也为任意值，包括 0 。

然而 对于匈牙利算法来说，难点并不在与程序本身，而是在如何把实际问题转化为最大二分图匹配的模型，然后再利用匈牙利算法解决。

HDOJ_1068  (二分图最大独立集=n-m/2)
HDOJ_1150  (二分图最小顶点覆盖=m)
HDOJ_1151  (二分图最小路径覆盖=n-m)
HDOJ_1281(求完美匹配的个数)
HDOJ_1498(最大匹配m=遍历每个点需要的次数)
在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是二分图的“最小顶点覆盖”。
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
节点数（n），最大匹配数（m）。