题目大意:

有p个课程和n个学生,每个学生可以自由选择课程(0到p个),现在要建立一个委员会,问是否能找到每个课程都有学生代表的集合,一个学生只能代表一个课程

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

 

简单的二分匹配,用匈牙利算法就可以,主要是练习模板,固定方法解题!

 

程序:

#include<stdio.h>
#include
<iostream>
using namespace std;
#define MAXN 305
int g[MAXN][MAXN];
int uN,vN;
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
int v;
for(v=1;v<=vN;v++)
if(g[u][v]&&!used[v])
{
used[v]
=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]
=u;
return true;
}
}
return false;
}
int hungary()
{
int res=0,u;
memset(linker,
-1,sizeof(linker));
for(u=1;u<=uN;u++)
{
memset(used,
0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main()
{
int u,v;
int T,i,n;
scanf(
"%d",&T);
while(T--)
{
scanf(
"%d%d",&uN,&vN);
memset(g,
0,sizeof(g));
for(u=1;u<=uN;u++)
{
scanf(
"%d",&n);
while(n--)
{
scanf(
"%d",&v);
g[u][v]
=1;
}
}
if(uN==hungary()) printf("YES\n");
else printf("NO\n");
}
return 0;
}

不好意思,感觉太简单了就没有加注释!!!匈牙利算法,详解可以看我前面几遍关于二分匹配的文章!