洛谷P1894 完美的牛栏 题解 二分图最大匹配模板题

题目链接：https://www.luogu.com.cn/problem/P1894

题目大意：求二分图最大匹配。

解题思路：hungary算法。

实现代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 220;
int n, m, linky[maxn];
bool vis[maxn];
vector<int> g[maxn];
bool dfs(int u) {
    int sz = g[u].size();
    for (int i = 0; i < sz; i ++) {
        int v = g[u][i];
        if (vis[v]) continue;
        vis[v] = true;
        if (!linky[v] || dfs(linky[v])) {
            linky[v] = u;
            return true;
        }
    }
    return false;
}
int hungry() {
    int cnt = 0;
    for (int i = 1; i <= n; i ++) {
        memset(vis+1, false, sizeof(bool)*m);
        if (dfs(i)) cnt ++;
    }
    return cnt;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int c, a;
        cin >> c;
        while (c --) {
            cin >> a;
            g[i].push_back(a);
        }
    }
    cout << hungry() << endl;
    return 0;
}