Phân Bổ Ca Trực Bác Sĩ Nội Trú

Buổi 48 — Min-Cost Max Flow
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Một bệnh viện có $N$ bác sĩ nội trú và $M$ ngày trực chuyên môn. Bác sĩ thứ $i$ chỉ có thể trực tối đa $L_i$ ngày trong đợt này. Ngày thứ $j$ cần đúng $R_j$ bác sĩ trực. Nếu bác sĩ $i$ nhận trực vào ngày $j$, bệnh viện cần chi trả mức phụ cấp $W_{i,j}$ (nếu $W_{i,j} = -1$ nghĩa là bác sĩ $i$ bận lịch mổ vào ngày $j$). Hãy tính tổng phụ cấp nhỏ nhất để xếp đủ người cho tất cả $M$ ngày trực.

Dữ liệu vào

Dòng 1 gồm hai số nguyên $N, M$ ($1 \le N, M \le 30$). Dòng 2 gồm $N$ số nguyên $L_i$ ($0 \le L_i \le M$). Dòng 3 gồm $M$ số nguyên $R_j$ ($0 \le R_j \le N$). $N$ dòng tiếp theo, mỗi dòng gồm $M$ số nguyên $W_{i,j}$ ($-1 \le W_{i,j} \le 1000$).

Dữ liệu ra

In ra tổng phụ cấp nhỏ nhất, hoặc -1 nếu không thể xếp đủ lịch trực.

Ví dụ
Input Output
3 3
2 2 2
2 1 2
3 4 2
5 1 3
2 6 4
11
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved