二分图匹配【p2147】课程

很明显的一个二分图匹配裸题,注意判断\(p >n\)时候,显然不能满足每一个课堂都有人,这个条件要在输入结束之后判断.

二分图匹配就不多BB了 qwq

代码

#include<cstdio>

#include<cctype>

#include<cstring>

#define clear(a) memset(a,0,sizeof a)

#define R register

using namespace std;

inline void in(int &x)

{

    int f=1;x=0;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

    while(isdigit(s)){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int T,n,p,match[20008];

int head[20008],tot,ans;

struct cod{int u,v;}edge[20008*4];

inline void add(int x,int y)

{

    edge[++tot].u=head[x];

    edge[tot].v=y;

    head[x]=tot;

}

bool vis[20008];

bool find(int x)

{

    for(R int i=head[x];i;i=edge[i].u)

    {

        if(!vis[edge[i].v])

        {

            vis[edge[i].v]=1;

            if(!match[edge[i].v] or find(match[edge[i].v]))

            {

                match[edge[i].v]=x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    in(T);

    while(T--)

    {

        in(p),in(n);ans=tot=0;

        clear(head);clear(match);clear(edge);clear(vis);

        for(R int i=1,x,y;i<=p;i++)

        {

            in(x);

            while(x--)

            {

                in(y);

                add(i,y);

            }

        }

        if(p>n){puts("NO");continue;}

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

        {

            clear(vis);

            if(find(i))ans++;

        }

        puts(ans==p?"YES":"NO");

    }

}