学步园

匈牙利算法。复杂度为O(mn)。

对每个点都找以它为起点的增广路，当找到增广路后，匹配数必定加1。

#include <stdio.h>
#include <string.h>

const int N = 105;
const int M = 10005;

struct Vertex
{
    int head;
}V[N];

struct Edge
{
    int v,next;
}E[M];

int top,match[N];

bool used[N];

void Init()
{
    top = 0;
    memset(V,-1,sizeof(V));
}

void Add_Edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
}

bool dfs(int u)
{
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(!used[v])
        {
            used[v] = true;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxMatch(int n)
{
    int ans = 0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if(dfs(i))
            ++ans;
    }
    return ans;
}

下面介绍几种应用到二分图匹配的常见问题模型。

为了方便，以下我们都设要选取的点集为 U ，总点集为 V，最大匹配的边集为 M。

1、最小顶点覆盖：在二分图中选取最少的点覆盖所有的边（边被覆盖是指被至少选取一个端点）。

1）|U| <= |M|。只需要去覆盖 M 中每条边即可。如果选完后不能覆盖所有的边，则把那条边加入 M，会使 M 变大，与 M 最大矛盾。

2）|U| >= |M|。由于 M 中任意两条边都无公共点，所以覆盖这些边至少就需要 |M| 个点。

2、最大独立集：在二分图中选取最多的点，使这些点互不相连。

1）|U| <= |V| - |M|。M 中每条边最多只能选取一个点放入 U，即至少有一个点不在 U 里面，从而一共至少 |M| 个点不在 U 里面。

2）|U| >= |V| - |M|。首先，不在 M 中出现的点一定都能放入 U，假如不能放，那么将导致相连的这条边加入 M，同样会使 M 变大，与 M 最大矛盾。

然后，M 中每条边至少选取一个点可以放入 U。如果两个点都不能放，那么肯定会出现一条增广路，使 M 变大，与 M 最大矛盾。

3、最小路径覆盖。