Bao phủ tập hợp

Buổi 11 — Brute Force & Sinh tổ hợp Implementation
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho tập vũ trụ $U = {1, 2, \ldots, N}$ và $M$ tập con $S_1, S_2, \ldots, S_M$ của $U$. Tìm số tập con ít nhất trong ${S_1, \ldots, S_M}$ sao cho hợp của chúng bằng $U$. Nếu không thể, in $-1$.

Dữ liệu vào
  • Dòng đầu: hai số nguyên $N$ và $M$ $(1 \le N \le 20, 1 \le M \le 20)$.
  • $M$ dòng tiếp theo: dòng thứ $i$ bắt đầu bằng $k_i$ (số phần tử của $S_i$), theo sau là $k_i$ số nguyên — các phần tử của $S_i$.
Dữ liệu ra
  • Một số nguyên — số tập con ít nhất, hoặc $-1$.
Ví dụ
Input Output
5 3\n3 1 2 3\n3 3 4 5\n2 1 5 2
3 2\n1 1\n1 2 -1
Giới hạn
  • $1 \le N \le 20$
  • $1 \le M \le 20$
Draft saved