【无聊放个模板系列】POJ 1274 (匈牙利)

时间:2021-11-14 21:58:50
 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
#define Maxn 210 int match[Maxn];
int n,m; struct node
{
int x,y,next;
}t[Maxn*Maxn];int len;
int first[Maxn]; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} bool chw[Maxn]; bool dfs(int x)
{
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(chw[y]) continue;
chw[y]=;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return ;
}
}
return ;
} void ffind()
{
int ans=;
memset(match,,sizeof(match));
for(int i=;i<=n;i++)
{
memset(chw,,sizeof(chw));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
len=;
memset(first,,sizeof(first));
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
while(x--)
{
int y;
scanf("%d",&y);
ins(i,y);
}
}
ffind();
}
return ;
}

2016-11-17 21:13:53

匈牙利