当然，匹配开始时我们任意选择一边的所有点为起始点找增广路径，由增广路的性质可以看出，每找到一条增广路径，匹配数增加1。

很多问题都可以转化为二分图匹配模型。二分图有如下几种常见变形：

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。

Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖 

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

(3)二分图的最大独立集

最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

匈牙利算法模板

邻接矩阵：

/* ***********************************************************
//二分图匹配（匈牙利算法的DFS实现）(邻接矩阵形式)
//初始化：g[][]两边顶点的划分情况
//建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配
//g没有边相连则初始化为0
//uN是匹配左边的顶点数，vN是匹配右边的顶点数
//调用：res=hungary();输出最大匹配数
//优点：适用于稠密图，DFS找增广路，实现简洁易于理解
//时间复杂度:O(VE)
//*************************************************************/
//顶点编号从0开始的
const int MAXN = 510;
int uN,vN;//u,v的数目，使用前面必须赋值
int g[MAXN][MAXN];//邻接矩阵
int linker[MAXN];
bool used[MAXN];

bool dfs(int u)
{
    for(int v = 0; v < vN; v++)         
        if(g[u][v] && !used[v])
        {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    return false;
}

int hungary()
{
    int res = 0;

    memset(linker,-1,sizeof(linker));
    for(int u = 0; u < uN; u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u))res++;
    }
    return res;
}

邻接表：

/*
* 匈牙利算法邻接表形式
* 使用前用init()进行初始化，给uN赋值
* 加边使用函数addedge(u,v)
*
*/
const int MAXN = 5010;//点数的最大值
const int MAXM = 50010;//边数的最大值
struct Edge
{
    int to,next;
} edge[MAXM];
int head[MAXN],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int linker[MAXN];
bool used[MAXN];
int uN;

bool dfs(int u)
{
    for(int i = head[u]; i != -1 ; i = edge[i].next)
    {
        int v = edge[i].to;
        if(!used[v])
        {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int res = 0;
    memset(linker,-1,sizeof(linker));
    for(int u = 0; u < uN; u++) //点的编号0~uN-1
    {
        memset(used,false,sizeof(used));
        if(dfs(u))res++;
    }
    return res;
}

Hopcroft-Karp算法

该算法由John.E.Hopcroft和Richard M.Karp于1973提出，故称Hopcroft-Karp算法。

原理

为了降低时间复杂度，可以在增广匹配集合M时，每次寻找多条增广路径。这样就可以进一步降低时间复杂度，可以证明，算法的时间复杂度可以到达O(sqrt(n)*e)，虽然优化不了多少，但在实际应用时，效果还是很明显的。

基本算法

该算法主要是对匈牙利算法的优化，在寻找增广路径的时候同时寻找多条不相交的增广路径，形成极大增广路径集，然后对极大增广路径集进行增广。在寻找增广路径集的每个阶段，找到的增广路径集都具有相同的长度，且随着算法的进行，增广路径的长度不断的扩大。可以证明，最多增广n^0.5次就可以得到最大匹配。

算法流程

（1）从G=(X,Y;E)中取一个初始匹配。

（2）若X中的所有顶点都被M匹配，则表明M为一个完美匹配，返回；否则，以所有未匹配顶点为源点进行一次BFS，标记各个点到源点的距离。

（3）在满足dis[v] = dis[u] + 1的边集<v,u>中，从X中找到一个未被M匹配的顶点x0，记S = {x0}，T = ￠。

（4）若N（S） = T，则表明当前已经无法得到更大匹配，返回；否则取一y0∈N(S) – 。

（5）若y0已经被M匹配则转步骤（6），否则做一条x0->y0的M-增广路径P（x0,y0）,取M = M△P（x0,y0）。

（6）由于y已经被M匹配，所以M中存在一条边（y0,z0）去S = S∪ {z0}，T = T∪{y0}，转步骤（2）。

算法具体时间与分析

在寻找增广路径中可以对X中的每个未匹配的顶点进行BFS，BFS时对每个顶点维护一个距离编号dx[nx],dy[ny]，如果某个Y中的节点为未匹配点，则找到一条增广路径。BFS结束后找到了增广路径集。然后利用DFS与匈牙利算法类似的方法对每条增广路进行增广，这样就可以找到最大匹配。

实现起来也并不复杂，对于两边各50000个点，200000条边的二分图最大匹配可以在1s内出解~~

const int MAXN = 300010;
const int INF = 0x3f3f3f3f;

vector<int>G[MAXN];
int uN;            //左端点数  编号0开始
int Mx[MAXN],My[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];

bool Search()
{
    queue<int>Q;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(int i=0; i<uN; i++)
    {
        if(Mx[i]==-1)
        {
            Q.push(i);
            dx[i]=0;
        }
    }
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        if(dx[u]>dis) break;
        int sz=G[u].size();
        for(int i=0; i<sz; i++)
        {
            int v=G[u][i];
            if(dy[v]==-1)
            {
                dy[v]=dx[u]+1;
                if(My[v]==-1)dis=dy[v];
                else
                {
                    dx[My[v]]=dy[v]+1;
                    Q.push(My[v]);
                }
            }
        }
    }
    return dis!=INF;
}

bool DFS(int u)
{
    int sz=G[u].size();
    for(int i=0; i<sz; i++)
    {
        int v=G[u][i];
        if(!used[v]&&dy[v]==dx[u]+1)
        {
            used[v]=true;
            if(My[v]!=-1&&dy[v]==dis)continue;
            if(My[v]==-1||DFS(My[v]))
            {
                My[v]=u;
                Mx[u]=v;
                return true;
            }
        }
    }
    return false;
}

int MaxMatch()
{
    int res=0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(Search())  //找极大最短增广路集
    {
        memset(used,false,sizeof(used));
        for(int i=0; i<uN; i++)
        {
            if(Mx[i]==-1&&DFS(i))
                res++;
        }
    }
    return res;
}

• 二分图匹配
• 匈牙利算法
• 匈牙利算法模板
• Hopcroft-Karp算法