1 人解决，9 人已尝试。
1 份提交通过，共有 63 份提交。
9.9 EMB 奖励。
2304. Protect Our Treasure!
单点时限: 2.0 sec
内存限制: 256 MB
A group of N pirates put their treasure in a chest. The pirates don’t trust each other (with good reason!) so they consult a locksmith. The locksmith puts L locks on the chest in a way that every lock must be unlocked to open the chest. Then he distributes keys to the locks to the pirates so that every pirate has some but not all of the keys. Any given lock can have multiple keys, but any given key can only open one lock.
Given a number of pirates and sets of keys assigned to each pirate, you must find all groups of pirates that together can open the chest, but do not contain any unnecessary members (i.e., the chest cannot be opened if any pirate is left out of the group).
Note that there will be too many pirates for you to simply examine all possible combinations of pirates, so you will need to be more intelligent in your choice of algorithms.
输入格式
The first line of input will be the number of pirates N, followed by the total number of locks L. Following will be a line for each pirate (1..N) listing the number(s) of the locks (1..L) to which the pirate has keys.
0<=N,L<=50
输出格式
The output will be all possible combinations of pirates that can open the chest. Each combination will be on a separate line, with the pirates listed in order from smallest to largest. The combinations must be listed in order of smallest number of pirates to largest required. For combinations with the same number of pirates, list the combinations in lexicographic order (i.e., compare the 1st pirates, breaking ties by comparing the 2nd pirates, then the 3rd, etc…).
样例
Input
3 3 1 3 1 2 2 3 /* 4 3 // 4 pirates, 3 keys 1 // pirate 1 has key to lock 1 2 // pirate 2 has key to lock 2 3 // pirate 3 has key to lock 3 1 2 // pirate 4 has keys to lock 1 and 2 */
Output
1 2 1 3 2 3 /* 3 4 1 2 3 */
题目标签