Description
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
Input
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
Output
程序运行结束时，将取数的最大总和输出
Sample Input
3 3
1 2 3
3 2 3
2 3 1
Sample Output
11
Hint
m,n<=100
题解
因为相邻两个数不能同时取的题设要求，像国际象棋棋盘一样染色 得到二分图
然后S向每个黑点连边，容量为点权
每个白点向T连边，容量为点权
最后每个黑点到能到的白点(上下左右)连边，容量为INF（表示这些边中需要割掉一些）
最后跑一遍最大流 利用最大流最小割定理可得此为最小割（最少要割掉的点权） ans=总点权-最小割
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=;
struct emm{
int e,f,v;
}a[];
int h[];
int tot=;
void con(int x,int y,int l)
{
if(y==-)return;
a[++tot].f=h[x];
h[x]=tot;
a[tot].e=y;
a[tot].v=l;
a[++tot].f=h[y];
h[y]=tot;
a[tot].e=x;
return;
}
int tu[][];
int num[][];
queue<int>q;
int d[];
int m,n,s,t;
bool bfs()
{
memset(d,,sizeof(d));
d[s]=;
q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=h[x];i;i=a[i].f)
if(!d[a[i].e]&&a[i].v)
{
d[a[i].e]=d[x]+;
q.push(a[i].e);
}
}
return d[t];
}
int dfs(int x,int al)
{
if(x==t||!al)return al;
int fl=;
for(int i=h[x];i;i=a[i].f)
if(d[a[i].e]==d[x]+&&a[i].v)
{
int f=dfs(a[i].e,min(a[i].v,al));
if(f)
{
fl+=f;
al-=f;
a[i].v-=f;
a[i^].v+=f;
if(!al)break;
}
}
if(!fl)d[x]=-;
return fl;
}
int main()
{
scanf("%d%d",&m,&n);
s=,t=m*n+;
int sum=;
for(int i=;i<=m;++i)
for(int j=;j<=n;++j)
{
scanf("%d",&tu[i][j]);
sum+=tu[i][j];
}
memset(num,-,sizeof(num));
int tim=;
for(int i=;i<=m;++i)
for(int j=;j<=n;++j)
num[i][j]=++tim;
for(int i=;i<=m;++i)
for(int j=;j<=n;++j)
if((i+j)%==)con(num[i][j],t,tu[i][j]);
else
{
con(s,num[i][j],tu[i][j]);
con(num[i][j],num[i-][j],INF);
con(num[i][j],num[i+][j],INF);
con(num[i][j],num[i][j-],INF);
con(num[i][j],num[i][j+],INF);
}
int ans=;
while(bfs())ans+=dfs(s,INF);
cout<<sum-ans;
return ;
}