网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
Work
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | worka.in | 输出文件 | worka.out |
第三题:work
当前有n(n<=12)个工作,和8个工人。现在每个工作需要占用一个工人的从[a,b]这个区间的时间(一个工人自然不可能在同一个时间做2个不同的工作),且一个工作不一定是所有工人都能够完成的。现在给出每个工作的描述,问是否存在一种安排方案使得所有工作都能完成。
输入文件(worka.in)
输出文件有多组数据。第一行一个数tot表示数据的组数,后面紧接tot组数据。
对于每一组数据的第一行有一个整数n,表示工作的数目。后面n行每行描述一个工作。
对于一个工作,a,b,k,h1,h2……hk来描述,表示这个工作需要占用一个工人[a,b]的时间,并且能够完成这个工作的工人只有k个,标号分别是h1,h2……hk。
输出文件(worka.out)
对于每组输入数据,输出一行YES(如果可以安排一种方案使得工作完成)或者是NO(无法安排一种方案)
样例:
input
2
2
1 1 1 1
2 2 1 1
2
1 2 1 1
2 2 1 1
output
YES
NO