学步园

题目链接:   poj 1274

题目大意:   给出N头奶牛，和M个牛棚

                  每头奶牛只在自己喜欢的牛棚产奶，问最大的产牛量

解题思路:   把N头奶牛作为X集合，M个牛棚作为Y集合

                  奶牛和牛棚的关系就是集合X和集合Y的关系

                  问题转化为 X集合和Y集合的最大匹配数

                  匈牙利DFS增广路求解

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 205
int edge[MAX][MAX],n,m,cx[MAX],cy[MAX],visit[MAX];

int DFS(int u)     //匈牙利DFS寻找增广轨
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(!visit[i]&&edge[u][i])
        {
            visit[i]=1;
            if(!cy[i]||DFS(cy[i]))
            {
                cx[u]=i;
                cy[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,sum,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        sum=0;
        memset(cx,0,sizeof(cx));
        memset(cy,0,sizeof(cy));
        memset(edge,0,sizeof(edge));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            for(j=1;j<=a;j++)
            {
                scanf("%d",&b);
                edge[i][b]=1;    //从X匹配到Y
            }
        }
        for(i=1;i<=n;i++)
        {
			if(!cx[i])
			{
			    memset(visit,0,sizeof(visit));
			    sum+=DFS(i);     //每次增广1
			}
        }
        printf("%d\n",sum);
    }
}