HDU1083 【匹配问题】

题意：

有P门课，N个学生，给出每门课上的人。

然后问你能不能使得每门课有一个课代表

思路：

课和学生是两类，且同类之间没有关系，构成二分图；直接就是一个最大匹配问题；

注意点：

1.是给课进行匹配不是学生

2.比如二分图有A,B两类，A与B允许编号相同，但是如果A中的点到B中的点建边，

这个意义是A对B有关系，B能去匹配A，这一定不是双向边，双向边就额外多了层关系啊，

而且如果有额外匹配空间是利用一个配偶数组（就是存匹配对象的配偶，其实就是A->B->A），然后去询问A还能不能额外在匹配一个；

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=6e4+10;

const int M=4e2+10;

struct asd{

    int to;

    int next;

};

asd q[N];

int head[N],tol;

int cy[M],p,n;

bool vis[M];

void init()

{

    tol=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

    q[tol].to=v;

    q[tol].next=head[u];

    head[u]=tol++;

}

bool Find(int u)

{

    for(int i=head[u];i!=-1;i=q[i].next)

    {

        int v=q[i].to;

        if(!vis[v])

        {

            vis[v]=true;

            if(cy[v]==-1||Find(cy[v]))

            {

                cy[v]=u;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

        int num,x;

        init();

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

            scanf("%d",&num);

            while(num--)

            {

                scanf("%d",&x);

                add(i,x);

            }

        }

        int ans=0;

        memset(cy,-1,sizeof(cy));

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

        {

            memset(vis,0,sizeof(vis));

            if(Find(i))

                ans++;

        }

        if(ans!=p)

            puts("NO");

        else

            puts("YES");

    }

    return 0;

}

巴特西

HDU1083 【匹配问题】

最新文章

热门文章