# Description
观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。
# Solution
- 网络流
题意即为选取一个点之后，当前点上下左右均不能选择，求选取的点的最大权值和。
所以我们把矩阵黑白染色，每个黑点向周围的 4 个白点连边，流量为正无穷。
然后建超级源点，超级汇点。源点向黑点连边，流量为黑点的权值；白点向汇点连边，流量为白点的权值。
然后我们对于这张图跑一个最小割，图中剩下的边权和就是能选取的最大和。
所以答案就是 减去最小割。最小割 = 最大流 相信大家都知道。
# Code
#include <bits/stdc++.h> | |
#define P(i, j) ((i - 1) * m + j) | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 2010; | |
const int INF = 2e9; | |
int n, m, sum, ans, s, t; | |
struct node{ | |
int v, w, nxt; | |
}edge[N << 1]; | |
int head[N], tot = 1; | |
int dx[4] = {-1, 0, 1, 0}; | |
int dy[4] = {0, 1, 0, -1}; | |
inline void add(int x, int y, int z){ | |
edge[++tot] = (node){y, z, head[x]}; | |
head[x] = tot; | |
} | |
int dep[N]; | |
inline bool bfs(){ | |
queue <int> q; | |
memset(dep, 0, sizeof(dep)); | |
q.push(s), dep[s] = 1; | |
while(!q.empty()){ | |
int x = q.front(); | |
q.pop(); | |
for(int i = head[x]; i; i = edge[i].nxt){ | |
int y = edge[i].v; | |
if(edge[i].w && !dep[y]) | |
dep[y] = dep[x] + 1, q.push(y); | |
} | |
} | |
return dep[t]; | |
} | |
inline int dfs(int x, int lim){ | |
if(x == t || !lim) return lim; | |
int flow = 0; | |
for(int i = head[x]; i; i = edge[i].nxt){ | |
int y = edge[i].v; | |
if(edge[i].w && dep[y] == dep[x] + 1){ | |
int res = dfs(y, min(lim, edge[i].w)); | |
lim -= res, flow += res, edge[i].w -= res, edge[i ^ 1].w += res; | |
} | |
} | |
if(!flow) dep[x] = 0; | |
return flow; | |
} | |
inline void dinic(){ | |
while(bfs()) ans += dfs(s, INF); | |
} | |
inline bool check(int x, int y){ | |
return x >= 1 && x <= n && y >= 1 && y <= m; | |
} | |
int main(){ | |
n = read(), m = read(); | |
t = P(n, m) + 1; | |
for(int i = 1, z; i <= n; ++i) | |
for(int j = 1; j <= m; ++j){ | |
sum += (z = read()); | |
if(!((i + j) & 1)){ | |
add(s, P(i, j), z), add(P(i, j), s, 0); | |
for(int k = 0; k < 4; ++k){ | |
int x = i + dx[k], y = j + dy[k]; | |
if(check(x, y)) add(P(i, j), P(x, y), INF), add(P(x, y), P(i, j), 0); | |
} | |
}else add(P(i, j), t, z), add(t, P(i, j), 0); | |
} | |
dinic(); | |
write(sum - ans), puts(""); | |
return 0; | |
} |
