Ghép nhóm theo sở thích
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Trường học có $N$ học sinh và $K$ câu lạc bộ (CLB). CLB thứ $j$ chỉ tiếp nhận tối đa $cap_j$ học sinh.
Mỗi học sinh $i$ đánh giá mức độ không hài lòng khi vào CLB $j$ là $C_{i,j}$ (hoặc -1 nếu học sinh đó từ chối vào CLB $j$). Mỗi học sinh chỉ được tham gia tối đa 1 CLB.
Hãy phân bổ sao cho số học sinh được vào CLB là nhiều nhất, và trong số các cách phân bổ đó, tổng mức độ không hài lòng là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, K$ ($1 \le N \le 200, 1 \le K \le 50$).
- Dòng thứ hai chứa $K$ số nguyên $cap_1, \dots, cap_K$ ($0 \le cap_j \le N$).
- $N$ dòng tiếp theo, mỗi dòng chứa $K$ số nguyên $C_{i,j}$ ($C_{i,j} = -1$ hoặc $0 \le C_{i,j} \le 10^5$).
Dữ liệu ra
- In ra hai số nguyên: số học sinh tối đa được nhận và tổng mức độ không hài lòng nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 2 2 1 3 5 4 2 -1 1 2 -1 |
3 6 |
Giới hạn
- $1 \le N \le 200, 1 \le K \le 50$.
- Thời gian chạy: 2 giây.
Community Discussion