POJ 1274 The Perfect Stall【二分图匹配】

题意： 有 n 牛，  m 个 房子，  每个牛都只住在自己想住的房子里面，一个房子只能住一个牛，问最多可以安排多少头牛入住。

分析:  求最大匹配。

#include<stdio.h>
#include<string.h>
#define clr(x)memset(x,0,sizeof(x))
struct node
{
    int to,next;
}q[40005];
int tot;
int head[202];
void add(int s,int u)
{
    q[tot].to=u;
    q[tot].next=head[s];
    head[s]=tot++;
}
int link[202];
bool v[202];
bool find(int x)
{
    int i,k;
    for(i=head[x];i;i=q[i].next)
    {
        k=q[i].to;
        if(!v[k])
        {
            v[k]=true;
            if(link[k]==0||find(link[k]))
            {
                link[k]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int sum,n,m,k,t,x,i;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        clr(head);  clr(link);
        tot=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&t);
            while(t--)
            {
                scanf("%d",&x);
                add(i,x);
            }
        }
        sum=0;
        for(i=1;i<=n;i++)
        {
            clr(v);
            if(find(i))
            sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}