SETCOV - Set Cover

no tags 

In the set cover problem there is a collection C = {S1, ...,Sm} of subsets of the universe [n] = {0, ...,n-1}, and one must find a minimum-sized subcollection of C that still covers [n] (it may be the case that Si and Sj contain the exact same elements for some ij). A path of length r is a graph on r+1 vertices v0, ...,vr where vi has an undirected edge to vi+1 for i = 0, ...,r-1 (these are the only edges). A set cover instance I is said to be path-realizable if there exists a mapping from I to a path of length m where the Si are mapped to edges in the path and each i in [n] is mapped to a pair of (not-necessarily distinct) vertices si, ti on the path such that the edges lying between si and ti correspond exactly to the sets of C that contain i. Two sets Si,Sj must be mapped to different edges on the path if ij. You will be given a set cover instance that is guaranteed to be path-realizable and should output the size of a minimum-sized subcollection of C still covering [n].


The first line of the input is "N M" (1 ≤ N, M ≤ 300), where N is the size of the universe and M is the number of sets Si in the collection of subsets of {0, ...,N - 1}. What follows are M groups of lines. The ith group starts with one line containing |Si|, the size of the ith subset. If |Si| = 0, the current group of lines ends. Otherwise the next line is a space-separated list of the elements contained in Si.


If [n] cannot be covered by a subcollection of C then you should output -1, followed by a newline. Otherwise, your output should consist of two lines. The first line is the size of a minimum-sized set cover. The second line is a space-separated list of the 0-based indices of the sets in an optimal set cover.


3 4
2 1
1 0

1 2

Added by:Minilek
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2007