Thành lập đội ngũ tương thích

Buổi 33 — Bitmask DP & SOS DP
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Công ty cần tuyển một đội ngũ để thực hiện dự án đòi hỏi $M$ kỹ năng (đánh số từ $1$ đến $M$). Có $N$ ứng viên, ứng viên thứ $i$ yêu cầu mức lương $C_i$ và sở hữu một tập các kỹ năng cho trước. Ngoài ra, có $P$ cặp ứng viên có mâu thuẫn với nhau và không thể cùng xuất hiện trong đội ngũ được chọn. Hãy tìm tổng chi phí thuê nhỏ nhất để đội ngũ được chọn sở hữu đầy đủ $M$ kỹ năng và không có hai thành viên nào mâu thuẫn với nhau. Nếu không có cách chọn hợp lệ, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, M, P$ ($1 \le N \le 20$, $1 \le M \le 16$, $0 \le P \le \frac{N(N-1)}{2}$).
  • $N$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng $C_i$ ($1 \le C_i \le 10^9$) và $K_i$ ($0 \le K_i \le M$), theo sau là $K_i$ số nguyên phân biệt trong $[1, M]$ là các kỹ năng của ứng viên $i$.
  • $P$ dòng cuối, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u < v \le N$) cho biết ứng viên $u$ và $v$ mâu thuẫn với nhau.
Dữ liệu ra
  • In ra tổng chi phí nhỏ nhất, hoặc -1 nếu không tồn tại đội ngũ hợp lệ.
Ví dụ
Input Output
3 3 1
10 2 1 2
15 2 2 3
5 1 3
1 3
25
2 2 1
5 1 1
5 1 2
1 2
-1
Giới hạn
  • $1 \le N \le 20$, $1 \le M \le 16$
  • $1 \le C_i \le 10^9$
Draft saved