Ghép Cặp Nghiên Cứu

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

Có $N$ nhà nghiên cứu ($N$ chẵn, $N \le 16$) cần được chia thành $N/2$ cặp để thực hiện dự án. Nếu nhà nghiên cứu $i$ và $j$ được ghép cặp với nhau, mức độ ăn ý của cặp này là $w_{i, j}$.

Hãy tìm cách chia $N$ người thành $N/2$ cặp sao cho tổng mức độ ăn ý của tất cả các cặp là lớn nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên chẵn $N$ ($2 \le N \le 16$).
  • $N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên $w_{i, j}$ ($0 \le w_{i, j} \le 10^6$, $w_{i, j} = w_{j, i}$, $w_{i, i} = 0$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng mức độ ăn ý lớn nhất.
Ví dụ
Input Output
4
0 3 1 5
3 0 6 2
1 6 0 4
5 2 4 0
11
Giới hạn
  • $2 \le N \le 16$, $N$ chẵn
  • $0 \le w_{i, j} \le 10^6$
Draft saved