1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include <iostream> #include <cstdio> #include <queue> #define maxn 100010 #define INF 1000000000 using namespace std;
int n, m;
inline int id(int i, int j) { return (i - 1) * m + j; }
int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 };
struct Edge { int to, next, w; } e[1000000]; int c1, head[maxn]; inline void add_edge(int u, int v, int w) { e[c1].to = v; e[c1].w = w; e[c1].next = head[u]; head[u] = c1++; }
inline void Add_edge(int u, int v, int w) { add_edge(u, v, w); add_edge(v, u, 0); }
int s, t, dep[maxn]; bool bfs() { fill(dep, dep + maxn, 0); dep[s] = 1; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (w > 0 && !dep[v]) { dep[v] = dep[u] + 1; Q.push(v); if (v == t) return 1; } } } return 0; }
int dfs(int u, int _w) { if (u == t || !_w) return _w; int s = 0; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (dep[v] == dep[u] + 1 && w > 0) { int di = dfs(v, min(_w - s, w)); e[i].w -= di; e[i ^ 1].w += di; s += di; if (s == _w) break; } } if (s < _w) dep[u] = 0; return s; }
int mf; int dinic() { while (bfs()) mf += dfs(s, INF); return mf; }
int ans; int main() { fill(head, head + maxn, -1); ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; s = 0; t = n * m + 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { int x; cin >> x; ans += x; if (i + j & 1) Add_edge(s, id(i, j), x); else Add_edge(id(i, j), t, x); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (i + j & 1) for (int k = 0; k < 4; ++k) { int x = i + dx[k], y = j + dy[k]; if (x < 1 || x > n || y < 1 || y > m) continue; Add_edge(id(i, j), id(x, y), INF); } cout << ans - dinic() << "\n"; return 0; }
|