二分图最大匹配匈牙利算法模板两种

1.邻接表（vector向量法）

vector<int> G[N];

int Search_Path(int s)
{
    for(int i=0;i<G[s].size();i++)
    {
        int v = G[s][i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(match[v] == -1 || Search_Path(match[v]))
            {
                match[v] = s;
                return 1;
            }
        }
    }
    return 0;
}

//主函数中

for(i=0;i<=n;i++)
        G[i].clear();
memset(match,-1,sizeof(match));
cnt = 0;
    for(i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Search_Path(i))
            cnt++;
    }

2.邻接表（前向星法）

struct Edge
{
    int v,next;
}G[N];

int Search_Path(int s)
{
    for(int i=first[s];i!=-1;i=G[i].next)
    {
        int v = G[i].v;
        if(!vis[v])
        {
            vis[v] = 1;
            if(match[v] == -1 || Search_Path(match[v]))
            {
                match[v] = s;
                return 1;
            }
        }
    }
    return 0;
}

//主函数里面一样

3.邻接矩阵法

int path[N][N];
int Search_Path(int s)
{
    for(int i=0;i<m;i++)
    {
        if(path[s][i] && !vis[i])
        {
            vis[i] = 1;
            if(match[i] == -1 || Search_Path(match[i]))
            {
                match[i] = s;
                return 1;
            }
        }
    }
    return 0;
}


//主函数中一样

附：HDU 2063 过山车

裸的二分图最大匹配。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1007

int path[N][N],vis[N];
int match[N];
int n,m;

int Search_Path(int s)
{
    for(int i=1;i<=m;i++)
    {
        if(path[s][i] && !vis[i])
        {
            vis[i] = 1;
            if(match[i] == -1 || Search_Path(match[i]))
            {
                match[i] = s;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int cnt,i,j,k;
    int a,b;
    while(scanf("%d",&k)!=EOF && k)
    {
        scanf("%d%d",&n,&m);
        memset(match,-1,sizeof(match));
        memset(path,0,sizeof(path));
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&a,&b);
            path[a][b] = 1;
        }
        cnt = 0;
        for(i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(Search_Path(i))
                cnt++;
        }
        printf("%d
",cnt);
    }
    return 0;
}