大家好,又见面了,我是全栈君,今天给大家准备了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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116823.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...