POJ 1274 COURSES：二分圖最大匹配（匈牙利算法）

題目大意

N 頭奶牛，M 個牛棚。每頭奶牛願意在某些牛棚產奶。每棚最多容納一頭牛，每頭牛最多分一個棚。求最大匹配數。
N,M ≤ 200，經典二分圖最大匹配。

匈牙利算法（DFS 增廣路）

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

int hungarian() {
    int ans = 0;
    fill(match, match+M+1, -1);
    for (int u=1; u<=N; u++) {
        fill(vis, vis+M+1, false);
        if (dfs(u)) ans++;
    }
    return ans;
}

完整代碼

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 205;
vector G[MAXN];
int match[MAXN], vis[MAXN];
int N, M;

int main() {
    while (~scanf("%d%d", &N, &M)) {
        for (int i=1; i<=N; i++) { G[i].clear(); }
        for (int i=1; i<=N; i++) {
            int cnt; scanf("%d", &cnt);
            for (int j=0; j