3303:Halls

题目描述

Managers of Tehran International Fair are experiencing the most difficult working days during the last 6 years. Recently, they are faced with a large number of requests to hire some of the fair halls. Each request consists of a list of candidate halls from which only one is needed by the requester, and the period of time during which the hall is needed to be hired. When there are only a few requests, the task of scheduling and allocating the halls to the requests are easy, but now, due to the large number of requests and the several overlaps between the requests, the task has been grown to an exhausting and time-consuming scheduling problem.

As a result, they have hired you, as a professional programmer, to write a program which is capable of doing the task of allocating halls to the requests automatically. What you are needed to do as the first phase of this project is to write a program that only indicates whether all the requests can be fulfilled with respect to the available resources or not.

输入解释

The first line of input contains a single integer T, which is the number of test cases. Each test case starts with a line containing one integer 1 ≤ R ≤ 12 which is the number of requests, followed by R lines, each of which containing the description of a single request. A request is a line containing the positive integers A B K H1 H2 ... HK, in which the period [A, B] (1 ≤ AB ≤ 10000) indicates the period during which a hall is needed, K indicates the number of candidate halls and 1 ≤ H1H2 ... ≤ HK ≤8 are the indices of the candidate halls from which a hall is to be allocated to that request.

输出解释

For each test case, your program should output a line containing the phrase "YES" if there is a way to fulfill all the requests. Otherwise it should output "NO".

输入样例
2
2
1 2 1 1
2 3 1 1
4
2 4 2 1 3
3 6 2 1 2
3 6 2 1 3
5 7 2 2 3
输出样例
NO
YES

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3303

最后修改于 2020-10-29 06:58:09 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536

·

·

·

·

登陆或注册以提交代码