Ghép cặp hoàn hảo cực đại
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ lập trình viên và $N$ dự án. Lập trình viên $i$ và dự án $j$ có thể ghép cặp với nhau nếu $W[i][j] > 0$, khi đó độ hài lòng thu được là $W[i][j]$. Nếu $W[i][j] = 0$, lập trình viên $i$ không thể làm dự án $j$. Hãy tìm một cách ghép cặp sao cho tổng độ hài lòng là lớn nhất có thể (không bắt buộc phải ghép hết tất cả $N$ cặp; mỗi lập trình viên làm tối đa một dự án và mỗi dự án có tối đa một lập trình viên).
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 16$).
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $W[i][j]$ ($0 \le W[i][j] \le 10^9$).
Dữ liệu ra
- In ra tổng độ hài lòng lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 3 5 0 0 0 3 4 0 6 0 |
15 |
| 2 0 0 0 0 |
0 |
Giới hạn
- $1 \le N \le 16$
- $0 \le W[i][j] \le 10^9$
Community Discussion