HDU 1083 Courses

题目链接：

acm.hdu.edu.cn/showproblem.php?pid=1082

题意描述：

给出课程数和学生数，以及每个课有哪些学生上过，问这N个学生能否组成一个委员会，该委员会中每人代表一种课，能否表示完P门课。

解题思路：

二分图最佳完备匹配，也即二分图最大匹配数。

AC代码：

#include<stdio.h>
#include<string.h>
int e[110][330],p,n,cp[110],cn[330],bn[330];
void maxmatch();
bool path(int u);
int main()
{
    int T,i,t,m;
    scanf("%d",&T);
    while(T--)
    {
        memset(e,0,sizeof(e));
        scanf("%d%d",&p,&n);
        for(i=1;i<=p;i++)
        {
            scanf("%d",&t);
            while(t--)
            {
                scanf("%d",&m);
                e[i][m]=1;
            }
        }
        maxmatch();
        for(i=1;i<=p;i++)
        {
            //printf("第%d门课由%d同学代表
",i,cp[i]);
            if(cp[i]==0)
            break;
        }
        if(i > p)
        printf("YES
");
        else
        printf("NO
");
    }
    return 0;
} 
void maxmatch()
{
    int i;
    memset(cp,0,sizeof(cp));
    memset(cn,0,sizeof(cn));
    for(i=1;i<=p;i++)
    {
        if(!cp[i])
        {
            memset(bn,0,sizeof(bn));
            path(i);
        }
    }
}
bool path(int u)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(e[u][i] && !bn[i])
        {
            bn[i]=1;
            if(!cn[i]  ||  path(cn[i]))
            {
                cn[i]=u;
                cp[u]=i;
                return 1;
            }
        }
    }
    return 0;
}