HDU 1083 网络流之二分图匹配

http://acm.hdu.edu.cn/showproblem.php?pid=1083

二分图匹配用得很多

这道题只需要简化的二分匹配

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxm 410

using namespace std;

int p,n;

int master[maxm];

int linking[maxm][maxm];

int has[maxm];

int solve(int x)//x课

{

    int i;

    for(i=;i<=n;i++)

    {

        if(linking[x][i]&&!has[i])

        {

            has[i]=;

            if(!master[i]||solve(master[i]))

            {

                master[i]=x;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    int m,sum=;

    scanf("%d",&m);

    while(m--)

    {

        scanf("%d%d",&p,&n);

        memset(master,,sizeof(master));

        memset(linking,,sizeof(linking));

        for(int i=;i<=p;i++)

        {

            int course;

            int student;

            scanf("%d",&course);

            for(int j=;j<=course;j++)

            {

                scanf("%d",&student);

                linking[i][student]=;

            }

        }

        for(int donser=;donser<=p;donser++)

        {

            memset(has,,sizeof(has));

            if(solve(donser)) sum++;

        }

        if(sum==p) printf("YES\n");

        else printf("NO\n");

        sum=;

    }

    return ;

}