R03467
Minimum Set Cover
골드 IV레이팅
의견: 0
설명
전체 집합은 \(\{0, 1, \dots, U-1\}\)이다. 이 집합의 부분집합 \(M\)개가 주어진다. 합집합이 전체 집합이 되도록 하는 최소 개수의 부분집합을 고르시오. 그 최소 개수를 출력하고, 전체를 덮을 수 없으면 \(-1\)을 출력한다.
제약
입력 형식
첫 줄에 \(U\)와 \(M\)이 주어진다 (\(1 \le U \le 16\), \(1 \le M \le 16\)). 이어지는 \(M\)개의 줄은 각각 하나의 부분집합을 나타내며, 정수 \(k\) 다음에 \([0, U-1]\) 범위의 서로 다른 원소 \(k\)개가 주어진다.
출력 형식
필요한 최소 부분집합 개수를 출력하고, 불가능하면 \(-1\)을 출력한다.
예제 1
입력
3 3
2 0 1
2 1 2
1 2
출력
2
예제 2
입력
3 2
1 0
1 1
출력
-1
예제 3
입력
4 3
2 0 1
2 2 3
1 0
출력
2
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그
평가 및 의견
Minimum Set Cover
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Minimum Set Cover
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기