匈牙利算法——二分图最大匹配问题

匈牙利算法求二分图的最大匹配数！

const int N = 100, M = 10000;

int h[N], ne[M], e[M], idx = 0;
int match[N];   // 记录每个节点的配对节点
bool st[N];     // 避免重复考虑点

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool find(x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    // 建图：虽然是无向图，但是加边时只需要将左边节点连向右边节点的边加入即可
    add(a, b);

    int ans = 0;  // 存匹配的数量
    for(int i = 1; i<=n1; i++)  //遍历左半边节点
    {
        memset(st, false, sizeof st);
        if(find(i)) ans++;
    }
    cout<<ans<<endl;

    return 0;
}

模板题