POJ1274.md

二分图匹配板子

#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 222;
int n,m,match[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];
bool dfs(int u){
    vis[u] = true;
    for(int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if(match[v]==-1||(!vis[match[v]]&&dfs(match[v]))){
            match[v] = u;
            return true;
        }
    }
    return false;
}
int solve(){
    memset(match,255,sizeof(match));
    int tot = 0;
    for(int i = 1; i <= n; i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) tot++;
    }
    return tot;
}
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 k; scanf("%d",&k);
            for(int j = 1; j <= k; j++){
                int v; scanf("%d",&v);
                G[i].push_back(v);
            }
        }
        printf("%d\n",solve());
    }
    return 0;
}