Courses HDU1083 -二分图匹配

题意：  p节课程，n个学生。询问是否能找到p个课代表，每个学生只能当一门课的课代表。

思路： 匈牙利裸匹配

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include <vector>
#include<algorithm>
using namespace std;

const int maxn=15005;
int n,m;
int pre[maxn];//保存各点的匹配点
int vis[maxn]; 
vector<int> vec[maxn];
int find(int u)//判断是否存在增广路，存在返回1
{
    int i,v;
    for(i=0;i<vec[u].size();i++)
    {
        v=vec[u][i];
        if(vis[v])continue;
        vis[v]=1;
        if(pre[v]==-1||find(pre[v]))//-1找到未盖点，find是增广路。
        {
            pre[v]=u;//匹配边和非匹配边交换 
            return 1;
        }
    }
    return 0;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        scanf("%d%d",&m,&n);
        int u,v;
        memset(pre,-1,sizeof(pre));
        for(int i=1;i<=n+m;i++)
            vec[i].clear();
        for(int i=1;i<=m;i++)
        {
            int k;
            scanf("%d",&k);
            for(int j=1;j<=k;j++)
            {
                scanf("%d",&v);
                v=v+m;
                vec[v].push_back(i);
                vec[i].push_back(v);
            }
        } 
        int ans=0;
        for(int i=1;i<=n+m;i++)
        {
            memset(vis,0,sizeof(vis));
            ans+=find(i);
        }
        if(ans==m*2 )
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}