匈牙利算法模板

　　匈牙利算法可以求解最大匹配数， 其基本思路是不断地寻找增广路， 由于增广路肯定是奇数个边，并且非匹配边比匹配边多一条， 因此找到增广路以后调换匹配边和非匹配边的就可以使匹配边多一条， 不断重复这个过程即可。。模板如下：

第二次整理：

struct Hungarian
{
    int n;    //顶点的数量
    int match[maxn];
    int check[maxn];
    vector<int> G[maxn];
    void init()
    {
        for(int i=0; i<=n; i++) G[i].clear();
    }
    void add_edge(int u, int v)
    {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bool dfs(int u)
    {
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i];
            if(!check[v])
            {
                check[v] = 1;
                if(match[v]==-1 || dfs(match[v]))
                {
                    match[u] = v;
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int hungarian()
    {
        int ans = 0;
        memset(match, -1, sizeof(match));
        for(int u=1; u<=n; u++)
        {
            if(match[u] == -1)
            {
                memset(check, 0, sizeof(check));
                if(dfs(u)) ++ans;
            }
        }
        return ans;
    }
}hun;

const int maxn = 1000 + 10;

struct Hungarian
{
    int n;         //顶点的数量
    int match[maxn];
    int check[maxn];
    vector<int> G[maxn];   //点的连接关系
    void Init()
    {
        for(int i=0; i<=n; i++)
            G[i].clear();
    }
    void AddEdge(int u, int v)
    {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bool dfs(int u)
    {
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i];
            if(!check[v])    //不在增广路中
            {
                check[v] = 1;
                if(match[v]==-1 || dfs(match[v]))
                {
                    match[u] = v;
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;    //不存在增广路
    }
    int hungarian()
    {
        int ans = 0;
        memset(match, -1, sizeof(match));
        for(int u=1; u<=n; u++)
        {
            if(match[u] == -1)
            {
                memset(check, 0, sizeof(check));
                if(dfs(u))
                    ++ans;
            }
        }
        return ans;
    }
}hun;

应用实例：USACO stall4

/*
    ID: m1500293
    LANG: C++
    PROG: stall4
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn = 1000 + 10;

struct Hungarian
{
    int n;         //顶点的数量
    int match[maxn];
    int check[maxn];
    vector<int> G[maxn];   //点的连接关系
    void Init()
    {
        for(int i=0; i<=n; i++)
            G[i].clear();
    }
    void AddEdge(int u, int v)
    {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bool dfs(int u)
    {
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i];
            if(!check[v])    //不在增广路中
            {
                check[v] = 1;
                if(match[v]==-1 || dfs(match[v]))
                {
                    match[u] = v;
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;    //不存在增广路
    }
    int hungarian()
    {
        int ans = 0;
        memset(match, -1, sizeof(match));
        for(int u=1; u<=n; u++)
        {
            if(match[u] == -1)
            {
                memset(check, 0, sizeof(check));
                if(dfs(u))
                    ++ans;
            }
        }
        return ans;
    }
}hun;

int main()
{
    freopen("stall4.in", "r", stdin);
    freopen("stall4.out", "w", stdout);
    int N, M;        //N个奶牛 M个围栏
    scanf("%d%d", &N, &M);
    hun.n = N+M;
    hun.Init();
    for(int i=1; i<=N; i++)
    {
        int num;
        scanf("%d", &num);
        while(num--)
        {
            int t;
            scanf("%d", &t);
            hun.AddEdge(i, N+t);
        }
    }
    printf("%d
", hun.hungarian());
    return 0;
}