| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 15655 | Accepted: 6185 |
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 Student1 1 Student1 2 ... Student1 Count1
Count2 Student2 1 Student2 2 ... Student2 Count2
...
CountP StudentP 1 StudentP 2 ... StudentP 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
一共有N个学生跟P门课程,一个学生可以任意选一门或多门课,问是否达成:
1.每个学生代表的都是不同的课（如果一个学生选修的那门课，那么他就可以代表这门课）
2.每门课都有一个代表
输入为:
P N(课程数跟学生数)
接着有P行,格式为Count studenti studenti+1 ……studentcount(Count表示对课程1感兴趣的学生数,接着有Count个学生)
如第一行2 1 2表示学生1跟学生2对课程1感兴趣
输出为:
若每门课都能找到一位代表则输出”YES”,否则为”NO”
假如有三个学生跟三门课程,学生1,2,3.为了跟学生区分,假设3个课程为4,5,6
左边节点是学生,右边节点是课程,下图表示,学生1对课程4,5感兴趣,学生2对课程5,6感兴趣,学生3对课程6感兴趣
于是问题就变为在二分图中寻找最大匹配,只要这个最大匹配大于或等于课程数P,那么就达到要求了.
#include<stdio.h>
#include<string.h>
int m,n;
int G[110][310],link[310];
bool vis[310];
int dfs(int x){
int i;
for(i=1;i<=m;i++){
if(G[x][i] && !vis[i]){
vis[i]=1;
if(link[i]==-1 || dfs(link[i])){
link[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int t,i,j,sum,num,tmp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
sum = 0;
memset(G,0,sizeof(G));
memset(link,-1,sizeof(link));
for(i=1;i<=n;i++){
scanf("%d",&num);
for(j=1;j<=num;j++){
scanf("%d",&tmp);
G[i][tmp]=1;
}
}
for(i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)==1) sum++;
}
printf("%s\n",sum==n?"YES":"NO");
}
return 0;
}