大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
解决报告
http://blog.csdn.net/juncoder/article/details/38136065
题意：
n个学生p门课程，每一个学生学习0或1以上的课程。
问：能否够组成委员会。满足
每一个学生代表一门不同的课程
一门课程在委员会中有一名代表
思路：
非常明显的二分图的完备匹配。
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 330
#define P 110
using namespace std;
int mmap[N+P][N+P],n,p,pre[N+P],vis[N+P],m,k;
int dfs(int x)
{
for(int i=p+1;i<=p+n;i++)
{
if(!vis[i]&&mmap[x][i])
{
vis[i]=1;
if(pre[i]==-1||dfs(pre[i]))
{
pre[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,t;
while(~scanf("%d",&t))
{
while(t--)
{
memset(mmap,0,sizeof(mmap));
memset(pre,-1,sizeof(pre));
scanf("%d%d",&p,&n);
for(i=1;i<=p;i++)
{
scanf("%d",&m);
for(j=1;j<=m;j++)
{
scanf("%d",&k);
mmap[i][k+p]=1;
}
}
int ans=0;
for(i=1;i<=p;i++)
{
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
if(ans==p)
printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 17166 | Accepted: 6748 |
Description
- every student in the committee represents a different course (a student can represent a course if he/she visits that course)
- each course has a representative in the committee
Input
P N
Count1 Student
1 1 Student
1 2 … Student
1 Count1
Count2 Student
2 1 Student
2 2 … Student
2 Count2
…
CountP Student
P 1 Student
P 2 … Student
P CountP
The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) – the number of courses and N (1 <= N <= 300) – the number of students. The next P lines describe in sequence of the courses �from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you抣l find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N.
There are no blank lines between consecutive sets of data. Input data are correct.
Output
Sample Input
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Sample Output
YES NO
Source
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116823.html原文链接：https://javaforall.net
