poj 1469 COURSES 题解
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 21515 | Accepted: 8455 |
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
Source
二分图最大匹配。
邻接矩阵map[i][j]表示j号喜欢i号课程,然后对课程进行寻找匹配,匹配成功则标记,之后统计匹配数目即可。
这题丧心病狂卡时,我改了两天,最后发现I/O超时了。。。 取消同步后的流还是略微慢一些,用标准输入输出可以正好卡过。TAT
/*
Problem:
OJ:
User:
Time:
Memory:
Length:
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iomanip>
#include<cassert>
#include<climits>
#include<vector>
#include<list>
#include<map>
#define maxn 1001
#define F(i,j,k) for(int i=j;i<=k;i++)
#define M(a,b) memset(a,b,sizeof(a))
#define FF(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x7fffffff
#define maxm 2016
#define mod 1000000007
//#define LOCAL
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,p;
bool kc[maxn][maxn];
bool vis[maxn];
int pp[maxn];
inline int path(int u)
{
int a,b,temp;
F(i,,n){
if(kc[u][i]&&!vis[i]){
vis[i]=true;
temp=pp[i];
pp[i]=u;
if(temp==-||path(temp)) return ;
pp[i]=temp;
}
}
return ;
}
inline int solve()
{
int a,b,ans=;
M(pp,-);
F(i,,p){
M(vis,);
// ans+=path(i);
if(path(i)) ans++;
if(ans==p) break;
}
return ans;
}
int main()
{
int t;cin>>t;
while(t--){
scanf("%d", &p);scanf("%d", &n);
M(kc,);
int num,cnt;
F(i,,p){
scanf("%d", &num);
F(j,,num){
scanf("%d", &cnt);
kc[i][cnt]=true;
}
}
if(solve()==p) printf("YES\n");
else printf("NO\n");
}
return ;
}
最新文章
- rsync密码使用要注意的几个点
- HA模式下历史服务器配置
- python基础学习二——第二天
- Git commit 常见用法
- Sublime-text 自己定义快捷键攻略
- Flash中用AS3做的游戏,导出apk安装到手机上滤镜效果出不来为什么?
- 在MySql中实现MemberShip的权限管理
- 解决mac下atom安装插件失败问题
- Swift2.2 看完这篇博客 你不想懂也会懂得----二叉树
- 解决 Linux error while loading shared libraries: cannot open shared object file: No such file or directory
- PageRank_网页排名_MapReduceJava代码实现思路
- css学习の第一四弹—代码格式简写归纳
- ubuntu数据库安装配置
- java学习笔记19(Arrays类)
- day4作业(基本运算流程if for)
- JavaScript进行简单的随即验证码生成(适合和我一样刚入门一本完整的教材书都没看完的弟弟)
- 网站前端优化技术 BigPipe分块处理技术
- 安卓程序代写 网上程序代写[原]Android开发技巧--ListView
- Java集合技巧
- Linux进程管理子系统