题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入格式
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
对于相邻的方格，横纵坐标之和奇偶性不同，那么将其分成两部分，形成二分图，求最小割即踢掉不符合条件的最小的数和，奇偶两部分分别连汇点和源点，边权为方格内的数，而两部分之间的边权取INF，保证割掉的是两个点之一的边权。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
const int maxn=1e4+5;
const int maxm=1e5+5;
const int INF=0x3f3f3f3f;
using namespace std;
struct node
{
int ver[maxm],nex[maxm],f[maxm],head[maxn],dep[maxn],cur[maxn];
int src,sink,tot,n;
ll ant;
void add(int u,int v,int flow)
{
ver[++tot]=v;
nex[tot]=head[u];
f[tot]=flow;
head[u]=tot;
ver[++tot]=u;
nex[tot]=head[v];
f[tot]=0;
head[v]=tot;
}
bool bfs()
{
queue<int> q;
memset(dep,-1,sizeof dep);
dep[src]=0;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nex[i])
{
int v=ver[i];
if(dep[v]==-1&&f[i])
{
dep[v]=dep[u]+1;
if(v==sink)
return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int mx)
{
if(u==sink)
return mx;
for(int &i=cur[u];i;i=nex[i])
{
int v=ver[i];
if(dep[v]==dep[u]+1&&f[i]>0)
{
int flow=dfs(v,min(mx,f[i]));
if(flow)
{
f[i]-=flow;
f[i^1]+=flow;
return flow;
}
}
}
return 0;
}
ll dinic(int s,int t)
{
this->src=s;
this->sink=t;
ant=0;
while(bfs())
{
for(int i=0;i<=n;i++)
{
cur[i]=head[i];
}
while(int d=dfs(src,INF))
{
ant+=d;
}
}
return ant;
}
void init(int n)
{
this->n=n;
memset(head,0,sizeof head);
tot=1;
}
}G;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main()
{
int n,m,s,t;
scanf("%d %d",&n,&m);
s=n*m+1;
t=n*m+2;
ll ant=0;
G.init(t+5);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
ant+=x;
if((i+j)&1)
{
G.add(s,(i-1)*m+j,x);
}
else
{
G.add((i-1)*m+j,t,x);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)&1)
{
for(int k=0;k<4;k++)
{
int ni=i+dx[k];
int nj=j+dy[k];
if(ni<1||ni>n||nj<1||nj>m)
continue;
G.add((i-1)*m+j,(ni-1)*m+nj,INF);
}
}
}
}
ant-=G.dinic(n*m+1,n*m+2);
printf("%lld
",ant);
return 0;
}