两道方格取数，第一道数据较小，可用状压dp求解，但是第二道数据增大1.5倍，状压就吃力了。
其实这里可以转化成最小割求解。
题意：
给你一个矩阵，矩阵中的每个数都有一定权值，当你取出其中一个数，与他上下左右相邻的数就不能被取。问你能取出的最大权值。
思路：
首先熟悉dp的人马上会想到。这是在一维相邻元素取舍的二位拓展。dp的思路易得。
但本人并不熟悉dp，只知道可写……
这里说的最小割解法。
先补一下所需前置知识。
- 二分图点权最大独立集：带点权二分图G中的一个子集V，其中一条边的两个端点不能同时属于V，且V中点权和最大。
- 点覆盖集：无向图G的一个点集，使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V’∈V，满足对于所有的(u,v)∈E,都有u属于V’或v属于V’成立，即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这些边恰好组成了原边集。
- 最小点覆盖集： 在无向图G中，点数最小的覆盖集。
- 最小点权覆盖集：在带点权无向图G中，点权之和最小的点覆盖集。
那么显然，点覆盖集的补集就是独立集，因为点覆盖集中每个边都至少被一个点覆盖，补集就不可能存在一条边的两个端点。
由此可得：二分图点权最大独立集=二分图点权和-二分图最小点权覆盖集
而二分图最小点权覆盖集可由最小割求得。
AC Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 3000;
const int inf = 0x3f3f3f3f;
int n, m, st, en, idx;
int level[maxn], cur[maxn];
int head[maxn];
int mat[60][60];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
struct node {
int to;
int nxt;
int flow;
} edges[20010];
queue<int> que;
inline void addEdge(int u, int v, int flow)
{
edges[idx].to = v;
edges[idx].flow = flow;
edges[idx].nxt = head[u];
head[u] = idx++;
edges[idx].to = u;
edges[idx].flow = 0;
edges[idx].nxt = head[v];
head[v] = idx++;
}
bool bfs()
{
while (!que.empty())
que.pop();
memset(level, -1, sizeof level);
que.push(st);
level[st] = 0;
int u;
while (!que.empty()) {
u = que.front();
que.pop();
for (int id = head[u]; ~id; id = edges[id].nxt) {
int v = edges[id].to;
if (edges[id].flow && level[v] == -1) {
level[v] = level[u] + 1;
que.push(v);
}
}
}
return level[en] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == en)
return low;
for (int& id = cur[u]; ~id; id = edges[id].nxt) {
int v = edges[id].to;
if (edges[id].flow && level[v] == level[u] + 1
&& (cflow = dfs(v, min(low, edges[id].flow)))) {
edges[id].flow -= cflow;
edges[id ^ 1].flow += cflow;
return cflow;
}
}
return 0;
}
int dinic()
{
int ans = 0, cflow;
while (bfs()) {
for (int i = st; i <= en; i++)
cur[i] = head[i];
while ((cflow = dfs(st, inf)))
ans += cflow;
}
return ans;
}
void init(int s, int e)
{
st = s, en = e;
memset(head, -1, sizeof head);
idx = 0;
}
int main()
{
int x, y;
while (scanf("%d %d", &n, &m) != EOF) {
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &mat[i][j]);
sum += mat[i][j];
}
init(0, n * m + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (((i + j) & 1) == 0) {
addEdge(st, (i - 1) * m + j, mat[i][j]);
for (int k = 0; k < 4; k++) {
x = i + dx[k];
y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > m)
continue;
addEdge((i - 1) * m + j, (x - 1) * m + y, inf);
}
} else
addEdge((i - 1) * m + j, en, mat[i][j]);
printf("%d\n", sum - dinic());
}
return 0;
}