Cân bằng ma trận ngân sách

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

Cho một ma trận số nguyên không âm $A$ kích thước $R \times C$. Bạn cần xây dựng một ma trận số nguyên không âm $B$ cùng kích thước $R \times C$ sao cho:

  • Tổng các phần tử trên hàng $i$ của $B$ đúng bằng $R_i$ (với mọi $1 \le i \le R$).
  • Tổng các phần tử trên cột $j$ của $B$ đúng bằng $C_j$ (với mọi $1 \le j \le C$).
  • Tổng sai lệch $\sum_{i=1}^R \sum_{j=1}^C |B_{i,j} - A_{i,j}|$ là nhỏ nhất.

Nếu không tồn tại ma trận $B$ thỏa mãn, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $R, C$ ($1 \le R, C \le 20$).
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $A_{i,j}$ ($0 \le A_{i,j} \le 1000$).
  • Dòng tiếp theo chứa $R$ số nguyên $R_1, \dots, R_R$ ($0 \le R_i \le 10^5$).
  • Dòng cuối cùng chứa $C$ số nguyên $C_1, \dots, C_C$ ($0 \le C_j \le 10^5$).
Dữ liệu ra
  • In ra tổng sai lệch nhỏ nhất, hoặc -1 nếu không tồn tại.
Ví dụ
Input Output
2 2
1 3
4 2
5 5
4 6
2
Giới hạn
  • $1 \le R, C \le 20$.
  • Thời gian chạy: 3 giây.
Draft saved