二分图最大匹配

二分图最大匹配，匈牙利算法

用dfs找增广路得到最大匹配，即为匈牙利算法

对于每一个左部点L1，如果能够在最大匹配的前提下找到一个右部点R1与之相连，

这个右部点R1必须满足的条件是R1无边，或者当前与R1相连的左部点L2能找到另一个右部点R2和自己相连，让出R1给L1

代码如下：

#include <cstdio>
#include <vector>

using namespace std;

int GtoB[505], id[505], vis[505];
vector <int> ve[505];

bool dfs(int u, int st)
{
    if(id[u]==st)
        return 0;
    else
    {
        int i;
        id[u] = st;
        for(i=0; i<ve[u].size(); i++)
        {
            int v = ve[u][i];
            //左u与右v连边的条件是右v无边 或 与右v相连的另一点能找到其他的边
            if(!vis[v] || dfs(GtoB[v], st))
            {
                vis[v] = 1;
                GtoB[v] = u;
                break;
            }
        }
        if(i<ve[u].size()) return 1;
        else return 0;
    }
}

int main()
{
    int n, m, k, u, v, ans;
    scanf("%d %d %d", &n, &m, &k);
    while(k--)
    {
        scanf("%d %d", &u, &v);
        ve[u].push_back(v);
    }
    ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(dfs(i, i))
            ans++;
    }
    printf("%d
", ans);
}