12-匈牙利算法

算法思想

算法图解

算法模板

import java.util.*;

public class Main {
    static int N = 510, M = 100010;
    static int n1, n2, m, idx;
    static int[] e = new int[M], ne = new int[M], h = new int[N];
    // match[i]存储右半点集中的 i 号点所匹配的左半点集中的节点的编号
    static int[] match = new int[N];
    // st[i]表示右半点集中的 i 号点，是否被左半点集中的点尝试连接过，无论是否成功
    static boolean[] st = new boolean[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n1 = in.nextInt();
        n2 = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);
        
        while(m -- > 0)
        {
            int u = in.nextInt(), v = in.nextInt();
            add(u, v);
        }
        
        // 求最大匹配数，
        // 遍历左半点集中的点，每个点尝试与右半集合中的所有点进行匹配        
        int res = 0;
        for(int i = 1; i <= n1; i ++ )
        {
            Arrays.fill(st, false);
            if(find(i)) res ++ ;
        }
        
        System.out.println(res);
    }
    
    static void add(int u, int x)
    {
        e[idx] = x;
        ne[idx] = h[u];
        h[u] = idx ++ ;
    }
    
    static boolean find(int u)
    {
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
                st[j] = true;
                
                // 右半点集中的 j 号点尚未匹配成功或者
                // 原来与其匹配的 k = match[j] 号点可以让出 j 号点（可以与其他节点匹配成功）
                if(match[j] == 0 || find(match[j]))
                {
                    match[j] = u;
                    return true; 
                }
            }
        }
        
        return false;
    }
}