$$\color{Red}{匈牙利算法（绿帽算法）-三种语言实现全解析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

匈牙利算法（绿帽算法）

1.算法原理

每当一个新男生想要找一个女生当对象时（为最大二分图添新边），就会看这个女生是否已经
匹配，如果匹配了男生，就让之前男生去换一个女生，以达到增加新边的目的。

2.算法细节

1.由于我们需要在匹配过程调用之前男生的点，故这里采用邻接表（稠密图）或者邻接矩阵（稀疏图）

bool find(int x)
{
    for(int i=h[x]; i!=-1; i=ne[i]){//当前男生去寻找所有可匹配女生
        int y = e[i];
        if(!st[y]){
            st[y] = true;//锁定不意味着匹配，是为了递归时让右点之前的左点去匹配别的点
            if(match[y] == 0 || find(match[y])){ //让之前左点匹配除该女生之外的点
                match[y] = x;
                return true;
            }}}
    return false;//之前左点所有女生都无法和他匹配，返回失败
}

2.尽管是无向图，但是事实上我们实际上只需要维持男生到女生这一条边
因此我们for循环左边所有的男生节点，其次，递归过程中使用match数组来表示当前女生的匹配男生

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

1. java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, n1, n2, m, idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] match = new int[N];
    static boolean[] st = new boolean[N];

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

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static boolean dfs(int father) {
        for (int i = h[father]; i != -1; i=ne[i]) {
            int son = e[i];
            if (st[son]) continue;
            st[son] = true;
            if (match[son] == 0 || dfs(match[son])) {
                match[son] = father;
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n1 = Integer.parseInt(s1[0]);
        n2 = Integer.parseInt(s1[1]);
        m = Integer.parseInt(s1[2]);
        for (int i = 0; i < m; i++) {
            String [] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a, b);
        }
        int res = 0;
        for (int i = 1; i <= n1; i++) {
            Arrays.fill(st, false);
            if (dfs(i))
                res ++;
        }
        System.out.println(res);
    }
}

2. python3 代码

N = 510
M = int(1e5+10)
h = [-1] * N
e = [0] * M
ne = [0] * M
idx = 0
match = [0] * N 

def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

def find(u):
    i = h[u]
    while i != -1:
        j = e[i]
        if not st[j]:
            #若找到一个女朋友暂时锁定，为了递归让其他人找另外人
            st[j] = True
            if match[j] == 0 or find(match[j]):
                match[j] = u
                return True
        i = ne[i]

    return False

if __name__ == '__main__':
    n1, n2, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        add(a, b)

    res = 0
    for i in range(1, n1+1):
        st = [False] * N
        if find(i):
            res += 1
    print(res)

3. C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx;
int n1, n2, m;
int match[N];
bool st[N];

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

bool find(int x)
{
    //当前男生去寻找所有可匹配女生
    for(int i=h[x]; i!=-1; i=ne[i])
    {
        int y = e[i];
        if(!st[y])
        {
            //先尝试锁定它，让之前匹配的左点去匹配别的点
            //锁定不意味着匹配，是为了让右点之前的左点去匹配别的点
            st[y] = true;
            //让之前左点匹配除该女生之外的点
            if(match[y] == 0 || find(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    //之前左点所有女生都无法和他匹配，返回失败
    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);

    memset(h, -1, sizeof h);

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

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

    printf("%d\n", res);

    return 0;
}