(color{#0066ff}{题目描述})
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
(color{#0066ff}{输入格式})
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
(color{#0066ff}{输出格式})
程序运行结束时，将取数的最大总和输出
(color{#0066ff}{输入样例})
3 3
1 2 3
3 2 3
2 3 1
(color{#0066ff}{输出样例})
11
(color{#0066ff}{数据范围与提示})
m,n<=100
(color{#0066ff}{题解})
最小割 = 最大流
通过把每个点横纵坐标相加的奇偶性，分为奇点和偶点
可以发现，奇点之间互不影响，偶点同理
S向所有奇点连边，所有偶点向T连边
奇点向相邻偶点连边
跑最大流（最小割）
最后用总数减就行了
#include <bits/stdc++.h>
#define LL long long
inline LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
const int max = 105050;
const int inf = 0x7fffffff;
struct node {
int to, dis;
node *nxt, *lst;
node(int to = 0, int dis = 0, node *nxt = NULL):to(to), dis(dis), nxt(nxt) {}
void *operator new (size_t) {
static node *S = NULL, *T = NULL;
return (S == T) && (T = (S = new node[1024]) + 1024), S++;
}
};
int rx[] = {0, 0, -1, 1};
int ry[] = {1, -1, 0, 0};
typedef node* nod;
nod head[max], cur[max];
int dep[max];
int id[120][120], mp[120][120];
std::queue<int> q;
int n, m, s, t;
int ans;
inline void add(int from, int to, int dis) {
nod o = new node(to, dis, head[from]);
head[from] = o;
}
inline void link(int from, int to, int dis) {
add(from, to, dis);
add(to, from, 0);
head[from]->lst = head[to];
head[to]->lst = head[from];
}
inline bool bfs() {
for(int i = s; i <= t; i++) dep[i] = 0, cur[i] = head[i];
dep[s] = 1;
q.push(s);
while(!q.empty()) {
int tp = q.front(); q.pop();
for(nod i = head[tp]; i; i = i->nxt) {
if(!dep[i->to] && i->dis > 0 ) {
dep[i->to] = dep[tp] + 1;
q.push(i->to);
}
}
}
return dep[t];
}
inline int dfs(int x, int change) {
if(x == t || !change) return change;
int flow = 0, ls;
for(nod i = head[x]; i; i = i->nxt) {
cur[x] = i;
if(dep[i->to] == dep[x] + 1 && (ls = dfs(i->to, std::min(change, i->dis)))) {
flow += ls;
change -= ls;
i->dis -= ls;
i->lst->dis += ls;
if(!change) break;
}
}
return flow;
}
inline int dinic() {
int flow = 0;
while(bfs()) flow += dfs(s, inf);
return flow;
}
int main() {
n = in(), m = in();
for(int cnt = 0, i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
id[i][j] = ++cnt, ans += (mp[i][j] = in());
s = 0, t = id[n][m] + 1;
for(int cnt = 0, i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if((i + j) & 1) {
link(s, id[i][j], mp[i][j]);
for(int k = 0; k < 4; k++) {
int xx = i + rx[k];
int yy = j + ry[k];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m)
link(id[i][j], id[xx][yy], inf);
}
}
else link(id[i][j], t, mp[i][j]);
}
printf("%d", ans - dinic());
return 0;
}