匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。 —————百度百科

思路

时间复杂夫

具体题目

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m, res;

int h[N], e[M], ne[M], idx;
int match[N]; // 配对
bool st[N];

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

bool find(int 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()
{
    memset(h, -1, sizeof(h));
    
    scanf("%d%d%d", &n1, &n2, &m);

    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }

    for(int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof(st));
        if(find(i)) res++;
    }

    cout << res << endl;
    
    return 0;
}