项目经理

import java.util.Arrays;
import java.util.Scanner;

/**
 * 匈牙利算法
 * 求二分图的最大匹配
 */
public class Main {
    // 存放A员工匹配的B员工id
    static int[] match;
    // B员工是否已匹配
    static boolean[] used;
    // A、B员工共同参与的项目，连线为1，不连线为0
    static int[][] map;

    public static int solve(int[] companyA, int[] companyB) {
        Arrays.fill(match, -1);
        int res = 0;
        for (int i : companyA) {
            Arrays.fill(used, false);
            if (find(companyB, i)) {
                res++;
            }
        }
        return res;
    }

    public static boolean find(int[] companyB, int index) {
        for (int j : companyB) {
            if (map[index][j] == 1 && !used[j]) {
                used[j] = true;
                if (match[j] == -1 || find(companyB, match[j])) {
                    match[j] = index;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String A = s.nextLine();
        String B = s.nextLine();
        String[] sa = A.split(" ");
        String[] sb = B.split(" ");
        int[] companyA = new int[sa.length];
        int[] companyB = new int[sb.length];
        int a = 0, b = 0;
        int maxa = 0, maxb = 0;
        for (String str : sa){
            int c = Integer.parseInt(str);
            companyA[a++] = c;
            maxa = Math.max(maxa, c);
        }
            
        for (String str : sb){
            int c = Integer.parseInt(str);
            companyB[b++] = c;
            maxb = Math.max(maxb, c);
        }
        match = new int[maxb+1];
        used = new boolean[maxb+1];
        map  = new int[maxa+1][maxb+1];
        
        int n = s.nextInt();
        while (n-- > 0) {
            int fir = s.nextInt();
            int sec = s.nextInt();
            map[fir][sec] = 1;
        }
        System.out.println(solve(companyA, companyB));
        s.close();
    }
}

import collections

a = list(map(int, input().split()))
b = list(map(int, input().split()))
n = int(input())


tmp1 = collections.defaultdict(list)
tmp2 = collections.defaultdict(list)
tmp3 = collections.defaultdict(set)
for i in range(n):
    x, y = list(map(int, input().split()))

    tmp3[x].add(y)
m = 20000
st = [False] * m
match = [-1] * m


def find(x, tmp):
    #print(x,match)
    for i in tmp[x]:
        #print(i)

        if st[i] == False:
            st[i] = True
            if (match[i] == -1 or find(match[i], tmp)):
                match[i] = x
                return True
    return False


res = 0

for i in a:
    if (find(i, tmp3)):
        st = [False] * m
        res += 1;
#print(match,a)
print(res)

二分图：一个二分图中的最大匹配数等于这个图中的最小点覆盖数
注意：

1. x-->y 可能有重复，最好用set筛一下
2. 莫名其妙数组越界，直接开到最大
3. 实际上是dfs

/**
   匈牙利算法
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    static int n, idx, N = 20010, M = 2 * N;
    static int[] h = new int[N], e = new int[M], ne = new int[M];
    static int[] v1 = new int[N], v2 = new int[N];
    static int[] match = new int[N];
    static boolean[] st = new boolean[N];
    static int res = 0;
    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = bf.readLine().split(" ");
        String[] brr = bf.readLine().split(" ");
        for(int i = 1; i <= arr.length; i ++ ){
            v1[i] = Integer.parseInt(arr[i - 1]);
        }
        for(int i = 1; i <= brr.length; i ++){
            v2[i] = Integer.parseInt(brr[i - 1]);
        }

        n = Integer.parseInt(bf.readLine());
        Arrays.fill(h, -1);
        for(int i = 1; i <= n; i ++){
            String[] crr = bf.readLine().split(" ");
            int a = Integer.parseInt(crr[0]), b = Integer.parseInt(crr[1]);
            add(a, b); add(b, a);
        }

        for(int i = 1; i <= arr.length; i ++){
            int u = v1[i];
            Arrays.fill(st, false);
            if(find(u))
                res ++;
        }

        System.out.println(res);

    }

    static boolean find(int u){

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

#include<bits/stdc++.h>

using namespace std;

vector<int> get(string s, int diff) {
    vector<int> a;
    stringstream str(s);
    int temp;
    while (str >> temp) a.push_back(temp + diff);
    return a;
}

const int maxn = 20100;
vector<vector<int>> e;
int match[maxn];
bool vis[maxn];
int ans;

bool dfs(int u) {
    for (int v:e[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> a, b;
    string s;
    getline(cin, s);
    a = get(s, 0);
    getline(cin, s);
    b = get(s, 0);
    int n;
    cin >> n;
    e = vector<vector<int>>(maxn);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
       // v+=10000;
        e[u].push_back(v);
        e[v].push_back(u);

    }
    ans = 0;
    memset(vis, 0, sizeof(vis));
    memset(match, -1, sizeof(match));
    for (int i = 0; i < a.size(); i++) {
        if (match[a[i]] == -1) {
            memset(vis, 0, sizeof(vis));
            if (dfs(a[i])) ans++;
        }
    }
    cout << ans << endl;
}