考虑一个包含 N 名学生和 P 门课程的群体。每个学生可以参加零门、一门或多门课程。你的任务是确定是否可以组成一个由恰好 P 名学生组成的委员会，同时满足以下条件：
- 委员会中的每名学生代表不同的课程（如果某学生参加了某课程，则该学生可以代表该课程）
- 每门课程在委员会中都有代表
程序应从文本文件中读取数据集。输入文件的第一行包含数据集的数量。每个数据集的格式如下：
P N
Count1 Student1_1 Student1_2 ... Student1_Count1
Count2 Student2_1 Student2_2 ... Student2_Count2
......
CountP StudentP_1 StudentP_2 ... StudentP_CountP
每个数据集的第一行包含两个正整数，中间用空格分隔：P (1 <= P <= 100) - 课程数量，N (1 <= N <= 300) - 学生数量。接下来的 P 行按顺序描述课程，从课程 1 到课程 P。每行描述一门课程，以一个整数 Count_i (0 <= Count_i <= N) 开始，表示参加该课程的学生数量。之后是一个空格，接着是 Count_i 个学生编号，每个学生编号之间用一个空格分隔。学生编号为 1 到 N 的正整数。
连续的数据集之间没有空行。输入数据正确。
程序的输出结果应在标准输出上。对于每个输入数据集，如果可以组成委员会，程序应输出一行 "YES"，否则输出 "NO"。输出行的开头不应有额外的空格。
示例输入和输出：
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
YES NO
代码：
#include
#include
#include
#include
#include
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
using namespace std;
const int N=330;
int map[N][N],link[N],vis[N];
int n,p;
bool dfs(int g)
{
for(int i=1;i<=n;i++)
{
if(map[g][i]==1&&vis[i]==0)
{
vis[i]=1;
if(link[i]==0||dfs(link[i]))
{
link[i]=g;
return true;
}
}
}
return false;
}
int main()
{
int t,h,m,cnt,i;
SI(t);
while(t--)
{
scanf("%d%d",&p,&n);
mem(map,0);
for(i=1;i<=p;i++)
{
SI(m);
for(int j=1;j<=m;j++)
{
SI(h);
map[i][h]=1;
}
}
mem(link,0);
cnt=0;
for(i=1;i<=p;i++)
{
mem(vis,0);
if(dfs(i))
cnt++;
}
if(cnt==p)
printf("YES\n");
else printf("NO\n");
}
return 0;
}
京公网安备 11010802041100号