POJ 1274 二分图匹配

匈牙利算法 裸题

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,p[8085],first[8888],next[8888],v[8888],tot,vis[8888],m,xx,yy,ans;
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
bool dfs(int x){
    for(int i=first[x];~i;i=next[i]){
        if(!vis[v[i]]){
            vis[v[i]]=1;
            if(!p[v[i]]||dfs(p[v[i]])){
                p[v[i]]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        memset(p,0,sizeof(p));
        memset(first,-1,sizeof(first)),ans=tot=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&xx);
            while(xx--){
                scanf("%d",&yy);
                add(i,200+yy),add(200+yy,i);
            }
        }
        for(int i=1;i<=n;i++){
            if(!p[i]){
                memset(vis,0,sizeof(vis));
                if(dfs(i))ans++;
            }
        }
        printf("%d
",ans);
    }
}