題目大意:

有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;
}

不好意思,感覺太簡單了就沒有加注釋!!!匈牙利算法,詳解可以看我前面幾遍關于二分匹配的文章!