«问题描述：
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入描述
Input Description
第1 行有2 个正整数m和n，分别表示棋盘的行数
和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。
输出描述
Output Description
将取数的最大总和输出
样例输入
Sample Input
3 3
1 2 3
3 2 3
2 3 1
样例输出
Sample Output
11
数据范围及提示 Data Size & Hint
n,m<=30
正解：网络流
解题报告：
同HDU1565，我的题解的传送门：http://www.cnblogs.com/ljh2000-jump/p/5756667.html
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const int inf = (<<);
int m,n,sum,S,T,ecnt,ans;
int a[MAXN][MAXN],deep[MAXN*MAXN];
int first[MAXN*MAXN];
queue<int>Q;
struct edge{
int next,to,f;
}e[MAXM]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void link(int x,int y,int z){
e[++ecnt].next=first[x]; first[x]=ecnt; e[ecnt].to=y; e[ecnt].f=z;
e[++ecnt].next=first[y]; first[y]=ecnt; e[ecnt].to=x; e[ecnt].f=;
} inline bool bfs(){
while(!Q.empty()) Q.pop();
for(int i=;i<=T;i++) deep[i]=;
Q.push(S); deep[S]=;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int i=first[u];i;i=e[i].next) {
int v=e[i].to;
if(e[i].f && !deep[v]) deep[v]=deep[u]+,Q.push(v);
}
}
if(deep[T]!=) return true;
return false;
} inline int Dinic(int x,int remain){
if(remain== || x==T) return remain;
int f,flow=;
for(int i=first[x];i;i=e[i].next) {
int v=e[i].to;
if(e[i].f && deep[v]==deep[x]+){
f=Dinic(v,min(remain,e[i].f));
if(f){
flow+=f; e[i].f-=f; e[i^].f+=f;
remain-=f; if(remain==) return flow;
} else deep[v]=-;
}
}
return flow;
} inline void work(){
m=getint(); n=getint();
for(int i=;i<=m;i++) for(int j=;j<=n;j++) a[i][j]=getint(),sum+=a[i][j];
S=m*n+;T=S+; ecnt=;
for(int i=;i<=m;i++) for(int j=;j<=n;j++) if((i+j)%==) link(S,(i-)*n+j,a[i][j]); else link((i-)*n+j,T,a[i][j]);//黑白染色
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
if((i+j)%) continue;
if(i!=) link((i-)*n+j,(i-)*n+j,inf);
if(j!=) link((i-)*n+j,(i-)*n+j-,inf);
if(j!=n) link((i-)*n+j,(i-)*n+j+,inf);
if(i!=m) link((i-)*n+j,i*n+j,inf);
}
while(bfs()) ans+=Dinic(S,inf);
printf("%d",sum-ans);
} int main()
{
work();
return ;
}