Language:
COURSES
Time Limit:1000MSMemory Limit:10000K
Total Submissions:18290Accepted:7204
Description
Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions: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
Your program should read sets of data from the std input. The first line of the input contains the number of the data sets. Each data set is presented in the following format:P NCount1 Student1 1Student1 2… Student1 Count1Count2 Student2 1Student2 2… Student2 Count2…CountP StudentP 1StudentP 2… StudentP CountPThe 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
The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.
Sample Input
23 33 1 2 32 1 21 13 32 1 32 1 31 1
Sample Output
YESNO
Source
题意：N个学生P门课程，每个学生见习0，1或更多课程。试判断是否能从这些学生中选出P名学生组成一个委员会同时满足以下条件：
1.委员会中的每名学生代表一门不同的课程
2.每门课程在委员会中有一名代表。
思路：求解二部图的最大匹配。不难发现，，只要匹配可以盖住每门课程，即匹配数与课程数量相等，委员会就可以组成。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 505#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rtypedef long long ll;using namespace std;int uN,vN;int mp[maxn][maxn];int linker[maxn];bool used[maxn];bool dfs(int u){for (int v=0;v<vN;v++){if (mp[u][v]&&!used[v]){used[v]=true;if (linker[v]==-1 || dfs(linker[v])){linker[v]=u;return true;}}}return false;}int hungary(){int ans=0;memset(linker,-1,sizeof(linker));for (int u=0;u<uN;u++){memset(used,false,sizeof(used));if (dfs(u)) ans++;if (ans==uN) break;}return ans;}int main(){int t,num,x;scanf("%d",&t);while (t–){scanf("%d%d",&uN,&vN);memset(mp,0,sizeof(mp));for (int i=0;i<uN;i++){scanf("%d",&num);while (num–){scanf("%d",&x);mp[i][x-1]=1;}}if (hungary()==uN) printf("YES\n");else printf("NO\n");}return 0;}
在旅途中，我遇见了你，你我相识是缘分！看着你手中的戒指，
