学步园

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

这是一个简单的求最大匹配的问题

有二种方法  

ac1

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool map[101][301];
bool mark[301];
int cx[101],cy[301]; //cx表示有多少门课  cy表示学生哦
int p,n;

int findpath(int u) //找出增广路径哦
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(map[u][i]&&!mark[i]) //注意u的位置哦
        {
            mark[i]=1;
           
            if(cy[i]==-1||findpath(cy[i]))
            {
                cy[i]=u;
                cx[u]=i;
                return 1;
            }
        }
    }
   return 0;
}

void maxmatch()  //找出最大匹配哦
{
    int i,j;
    int res=0;
    for(i=1;i<=p;i++)
     cx[i]=-1;

    for(j=1;j<=n;j++)
     cy[j]=-1;

    for(i=1;i<=p;i++)
    {
        if(cx[i]==-1)
        {
            for(j=1;j<=n;j++)
            mark[j]=0;

            res+=findpath(i);
        }
    }

    if(res>=p) {cout<<"YES"<<endl; return ;}
    else cout<<"NO"<<endl;
}

int main()
{
    int i,j,k,m;
    cin>>k;
    while(k--)
    {
        memset(map,false,sizeof(map));
        cin>>p>>n;
        for(i=1;i<=p;i++)
        {
            cin>>j;
            for(int h=1;h<=j;h++)
            {
                cin>>m;
                map[i][m]=1;
            }
        }

        maxmatch();

    }
    return 0;
}

   ac2

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool map[301][301];
bool mark[301];
int link[301]; //cx表示有多少门课  cy表示学生哦
int p,n;

int findpath(int u)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(map[u][i]&&!mark[i])
        {
            mark[i]=1;
            //这里到底是cx还是cy呢？

            if(!link[i]||findpath(link[i]))
            {
                link[i]=u;
                return 1;
            }
        }
    }
   return 0;
}

void maxmatch()
{
    int i,j;
    int res=0;

    for(j=1;j<=n;j++)
     link[j]=0;

    for(i=1;i<=p;i++)
    {
        for(j=1;j<=n;j++)
        mark[j]=0;

        res+=findpath(i);
    }

    if(res>=p) {cout<<"YES"<<endl; return ;}
    else cout<<"NO"<<endl;
}

int main()
{
    int i,j,k,m;
    cin>>k;
    while(k--)
    {
        memset(map,false,sizeof(map));
        memset(link,false,sizeof(link));

        cin>>p>>n;
        for(i=1;i<=p;i++)
        {
            cin>>j;
            for(int h=1;h<=j;h++)
            {
                cin>>m;
                map[i][m]=1;
            }
        }

        maxmatch();
       // cout<<"ddddddddddddd1"<<endl;
    }
    return 0;
}