[USACO4.2] The Perfect Stall – 二分图最大匹配

有 \(N\) 牛 \(M\) 棚，第 \(i\) 头牛只能待在给定的一个牛棚集合里，一个牛棚只能容纳一头牛。求最多装多少头牛。 \(N,M \leq 200\)

Solution

难度：L1

二分图最大匹配裸题

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n,m,p,cx[N],cy[N],vis[N];
std::vector<int> e[N];
int dfs(int u,int Time) {
    for(int i=0;i<(int)e[u].size();++i) {
        int v=e[u][i];
        if(vis[v]^Time) {
            vis[v]=Time;
            if(!cy[v]||dfs(cy[v],Time)) {
                cx[u]=v; cy[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++) {
        int t;
        cin>>t;
        while(t--) {
            int x;
            cin>>x;
            e[i].push_back(x);
        }
    }
    for(int i=1;i<=n;++i) ans+=dfs(i,i);
    cout<<ans<<endl;
    return 0;
}