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

题意:
有p门课和n个学生,每个学生都选了若干门课,每门课都要找一个同学来表演,且一个同学只能表演一门课,判断是否能行。

思路:
二分图匹配的模板题。

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int p, n;
int G[][];
int vis[];
int match[]; //第i学生的选课 int dfs(int x)
{
for (int i = ; i <= n; i++)
{
if (G[x][i] && !vis[i])
{
vis[i] = ; //标记,为了为了后面改课时跳过这门课
if (!match[i] || dfs(match[i])) //如果该学生还没有确定课或者这门课换一个学生
{
match[i] = x;
return ;
}
}
}
return ;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int T;
int a;
cin >> T;
while (T--)
{
memset(match, , sizeof(match));
memset(G, , sizeof(G));
cin >> p >> n;
int num;
for (int i = ; i <= p; i++)
{
cin >> num;
while (num--)
{
cin >> a;
G[i][a] = ;
}
}
//为每门课匹配学生
int i;
for (i = ; i <= p; i++)
{
memset(vis, , sizeof(vis));
if (!dfs(i)) break;
}
if (i == p + ) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
05-11 15:48