题目大意: 一个 N*M 的网格，每个单元都有一块价值 Cij 的宝石。问最多能取多少价值的宝石且任意两块宝石不相邻。（1 <= N, M <= 50, 0 <= Cij <= 40000）
建图方法：
先对网格进行黑白染色，
然后所有黑点到S有一条容量为Cij的边，
白点到T有一条容量为Cij的边，
黑点和相邻的白点有一条容量为INF的边.
最后答案就是 所有的Cij之和减去最小割
自己的理解：每一条边如果流满相当于放弃这一种宝石，并且所以最小割保证放弃的价值最少。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=,INF=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str;
}
int head[N],num=;
struct Lin{
int next,to,dis;
}a[N*];
void init(int x,int y,int z){
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
a[++num].next=head[y];
a[num].to=x;
a[num].dis=;
head[y]=num;
}
int val[][],id[][],ids=,S=,T,ans=;
int mx[]={,,,-},my[]={,-,,};
int q[N],dep[N];
bool bfs()
{
memset(dep,,sizeof(dep));
int x,u,t=,sum=;
q[]=S;dep[S]=;
while(t!=sum)
{
x=q[++t];
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u]||a[i].dis<=)continue;
dep[u]=dep[x]+;q[++sum]=u;
}
}
return dep[T];
}
int dfs(int x,int flow)
{
if(x==T || !flow)return flow;
int u,tmp,sum=;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u]!=dep[x]+ || a[i].dis<=)continue;
tmp=dfs(u,min(flow,a[i].dis));
a[i].dis-=tmp;a[i^].dis+=tmp;
sum+=tmp;flow-=tmp;
if(!flow)break;
}
return sum;
}
int maxflow(){
int tot=,tmp;
while(bfs()){
tmp=dfs(S,INF);
while(tmp)tot+=tmp,tmp=dfs(S,INF);
}
return tot;
}
void work()
{
int n=gi(),m=gi(),flag,xx,yy;
T=n*m+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
val[i][j]=gi();id[i][j]=++ids;ans+=val[i][j];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
flag=((i+j)&);
if(flag)init(S,id[i][j],val[i][j]);
else init(id[i][j],T,val[i][j]);
if(!flag)continue;
for(int k=;k<;k++){
xx=i+mx[k];yy=j+my[k];
if(xx>n || xx< || yy>m || yy<)continue;
init(id[i][j],id[xx][yy],INF);
}
}
printf("%d\n",ans-maxflow());
}
void Clear(){
memset(head,,sizeof(head));
num=;ids=;ans=;
}
int main()
{
int TT=gi();
while(TT--){
work();
Clear();
}
}