Lưới Chiến Thuật

Buổi 47 — Luồng cực đại (Dinic)
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một bảng lưới kích thước R x C, mỗi ô (i, j) có giá trị nguyên không âm a_{i,j}. Bạn cần chọn một tập các ô sao cho không có hai ô nào được chọn chung cạnh với nhau, đồng thời tổng giá trị các ô được chọn là lớn nhất có thể.

Dữ liệu vào
  • Dòng đầu: hai số nguyên R và C (1 ≤ R, C, R × C ≤ 484).
  • R dòng tiếp theo, mỗi dòng chứa C số nguyên a_{i,j} (0 ≤ a_{i,j} ≤ 10^9).
Dữ liệu ra
  • Một số nguyên duy nhất: tổng giá trị lớn nhất có thể chọn.
Ví dụ
Input Output
2 2\n1 2\n3 4 5
Giới hạn
  • R × C ≤ 484
  • 0 ≤ a_{i,j} ≤ 10^9
Draft saved