[USACO4.2] 完美的牛栏The Perfect Stall

wh2011 · 2023-11-05 15:04:40 · 个人记录

二分图板子，二分图有句名言，匈牙利算法(指二分图)准则：待字闺中，据为己有；名花有主，求他放手。

code:

#include <bits/stdc++.h>
#include <cstdio>
#define rep(x, y, z) for (int x = y; x <= z; ++x)
#define per(x, y, z) for (int x = y; x >= z; --x)
#define mem(a, x) memset(a, x, sizeof a)
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all() x.begin(), x.end()
#define x first
#define y second
#define swap(a, b) a = a ^ b, b = b ^ a, a = a ^ b
#define pd push_back
#define endl '\n'
#define il inline
using namespace std;
using ll = long long;
using db = double;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
int rd() {int s = 0, fu = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') fu = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar();} return s * fu;}
void rt(int x) {int sta[20], tt = 0; if (x < 0) putchar('-'), x = -x; do sta[tt++] = x % 10, x /= 10; while (x); while (tt) putchar(sta[--tt] ^ 48);}
void sao(int x) {rt(x); putchar(' ');}
void wao(int x) {rt(x); putchar('\n');}
int qmi(ll a, int b) {ll res = 1; while (b) {if (b & 1) res = res * a; a = a * a; b >>= 1;} return res;}
int qmi(ll a, int b, int p) {ll res = 1 % p; while (b) {if (b & 1) res = res * a % p; a = a * a % p; b >>= 1;} return res;}

const int N = 210;
bool st[N], g[N][N];
int match[N], n, m, ans;

bool find(int u) {
    for (int i = 1; i <= m; ++i){
        if (!g[u][i]) continue;
        if (st[i]) continue;
        st[i] = true;
        if (!match[i] || find(match[i])) {
            match[i] = u;
            return true;
        }
    }
    return false;
}

int main() {
    n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        int cnt = rd();
        while (cnt--) {
            int a = rd();
            g[i][a] = true;
        }
    }
    for (int i = 1; i <= n; ++i) {
        memset(st, false, sizeof st);
        ans += find(i);
    }
    rt(ans);
    return 0;
}